15. 三数之和 2-526互联

2023-11-09

思路：

此题并不适合哈希表法，去重问题很麻烦

用双指针法，但是注意：双指针法如果不优化（也就是3层暴力）是超时的

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //三者都不相同，和为0
        //可以作为i》j》k   不影响的 
        //可能有多个
 
        //暴力法  3层循环，有点bt
        //借用哈希表，变为2层循环
 
 
        //会有去重问题
        //可以进一步思考-》nums[i]<=nums[j]<=nums[k]
        //进一步思考-》可以先将数组就行排序
        //还是有去重问题，此题不适合哈希表法，适合双指针
 
        List<List<Integer>> res=new ArrayList<>();
 
        Arrays.sort(nums);
 
        for(int i=0;i<nums.length;){
 
            for(int j=i+1;j<nums.length;){
 
                for(int k=j+1;k<nums.length;){
 
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> l=new ArrayList<>();
                        l.add(nums[i]);
                        l.add(nums[j]);
                        l.add(nums[k]);
                        res.add(l);
                    }
 
                    int z=nums[k];
                    k++;
                    while(k<nums.length && nums[k]==z){
                        k++;
                    }
 
                }
 
 
                int y=nums[j];
                j++;
                while(j<nums.length && nums[j]==y){
                    j++;
                }
 
 
            }
 
            int x=nums[i];
            i++;
            while(i<nums.length && nums[i]==x){
                i++;
            }
        }
 
        return res;
 
    }
}

下面是双指针优化内层的2个循环，使得o（n3）变为o（n2）

若和大于 0，说明 nums[R]nums[R]nums[R] 太大，R 左移
若和小于 0，说明 nums[L]nums[L]nums[L] 太小，L 右移

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //三者都不相同，和为0
        //可以作为i》j》k   不影响的 
        //可能有多个
 
        //暴力法  3层循环，有点bt
        //借用哈希表，变为2层循环
 
 
        //会有去重问题
        //可以进一步思考-》nums[i]<=nums[j]<=nums[k]
        //进一步思考-》可以先将数组就行排序
        //还是有去重问题，此题不适合哈希表法，适合双指针
 
         int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third) {
                    break;
                }
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
 
 
 
    }
}