day13

三数之和

卡了俩月的双指针,微笑

class Solution {
    //定义三个指针，保证遍历数组中的每一个结果
    //画图，解答
    public List<List<Integer>> threeSum(int[] nums) {
        //定义一个结果集
        List<List<Integer>> res = new ArrayList<>();
        //数组的长度
        int len = nums.length;
        //当前数组的长度为空，或者长度小于3时，直接退出
        if(nums == null || len <3){
            return res;
        }
        //将数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for(int i = 0; i<len;i++){
            //如果遍历的起始元素大于0，就直接退出
            //原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
            if(nums[i]>0){
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int l = i +1;
            int r = len-1;
            //当 l 不等于 r时就继续遍历
            while(l<r){
                //将三数进行相加
                int sum = nums[i] + nums[l] + nums[r];
                //如果等于0，将结果对应的索引位置的值加入结果集中
                if(sum==0){
                    // 将三数的结果集加入到结果集中
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                    //如果重复，直接跳过。
                    //去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                    while(l < r && nums[l] == nums[l+1]) {
                        l++;
                    }
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while(l< r && nums[r] == nums[r-1]){
                        r--;
                    } 
                    //将 左指针右移，将右指针左移。
                    l++;
                    r--;
                    //如果结果小于0，将左指针右移
                }else if(sum < 0){
                    l++;
                    //如果结果大于0，将右指针左移
                }else if(sum > 0){
                    r--;
                }
            }
        }
        return res;
    }
}

无重复的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
这道题很巧妙的使用了滑动窗口
其中保持end端不断的前进,start通过动态的查找进行判断最长的字串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int ans = 0;
        Map<Character,Integer> map = new HashMap<>();
        //start的位置保持变化,end的位置不变
        for(int end = 0,start = 0; end<n ; end++){
            char alpha = s.charAt(end);
            if(map.containsKey(alpha)){
                start = Math.max(map.get(alpha),start);
            }
            ans = Math.max(ans,end-start+1);
            map.put(s.charAt(end),end+1);
        }
        return ans;
    }
} 

找到字符串中所有的异位词

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // 检查输入是否为空或 p 的长度大于 s 的长度
        if (s.isEmpty() || p.isEmpty() || p.length() > s.length()) {
            return new ArrayList<>(); // 返回空列表
        }

        int sLen = s.length(); // 获取字符串 s 的长度
        int pLen = p.length(); // 获取字符串 p 的长度

        int[] arr = new int[128]; // 创建大小为 128 的数组，用于记录字符串 p 中每个字符的出现次数
        // 遍历字符串 p，统计每个字符的出现次数
        for (int i = 0; i < pLen; i++) {
            arr[p.charAt(i)]++;
        }

        List<Integer> resultList = new ArrayList<>(); // 创建结果列表
        int[] matchArr = new int[128]; // 创建大小为 128 的数组，用于记录窗口内子串的字符出现次数
        // 遍历字符串 s，维护一个长度为 pLen 的窗口
        for (int i = 0; i < sLen; i++) {
            matchArr[s.charAt(i)]++; // 添加窗口最右边的字符的出现次数

            // 如果窗口的长度大于等于 p 的长度
            if (i >= pLen - 1) {
                // 比较窗口内的字符出现次数数组和 p 的字符出现次数数组是否相等
                if (Arrays.equals(arr, matchArr)) {
                    // 如果相等，将窗口的起始索引加入结果列表
                    resultList.add((i + 1) - pLen);
                }
                matchArr[s.charAt((i + 1) - pLen)]--; // 移除窗口最左边的字符的出现次数
            }
        }

        return resultList; // 返回结果列表
    }
}

轮转数组

注意System.arraycopy()方法的用法。

class Solution {
    public void rotate(int[] nums, int k) {
        int []ans = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            int temp = 0;
            temp=(i+k)%nums.length;
            ans[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(ans,0,nums,0,nums.length);
    }
}

除自身以外的整数积

使用从左边遍历一遍,从右边遍历一遍,然后进行求积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] l = new int[n];
        int[] r = new int[n];
        int[] res = new int [n];
        l[0]=1;
        r[n-1]=1;
        res[0]=1;
        for(int i = 1;i<n;i++){
            l[i]=l[i-1]*nums[i-1];
        }
        for(int i = n-2;i>=0;i--){
            r[i]=r[i+1]*nums[i+1];
        }
        for(int i = 0;i<n;i++){
            res[i]=r[i]*l[i];
        }
        return res;
    }
}

矩阵置零

通过设置两个标记位数组,第一遍遍历进行设置,第二遍遍历进行置零

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean [] row = new boolean[m];
        boolean [] col = new boolean[n];
        for(int i = 0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j]==0){
                    row[i]=true;
                    col[j]=true;
                }
            }
        }
        for(int i = 0; i<m; i++){
            for(int j=0; j<n; j++){
                if(row[i]==true||col[j]==true){
                    matrix[i][j]=0;
                }
            }
        }
    }
}