剑指offer015 三数之和

# 暴力循环法
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set set = new HashSet();
        int[] temp = new int[3];
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (i != j && i != k && j != k && nums[i] + nums[j] + nums[k] == 0) {
                       set.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        List list = new ArrayList(set);
       return list;
    }  
}

时间复杂度 O( n^3 )

# 双指针
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set set = new HashSet();

        for (int i = 0; i < nums.length; i++) {
            int left = i+1;
            int right = nums.length - 1;
            int Target = -nums[i];   //目标值=和的相反数
            while (left < right) {
                int total = nums[left] + nums[right];
                if (total > Target) {
                    right--;
                } else if (total < Target) {
                    left++;
                } else {
                   set.add( Arrays.asList(nums[left], nums[right], nums[i]));
                    right--;
                    left++;  
                    //因为不止一组数据，比如 目标值nums【0】= nums【1】+nums【n-1】成功匹配
                    //那么继续 目标値为【1】？= nums
                }
            }
        }

            return new ArrayList<>(set);
    }
      
    }  

时间复杂度 O (n^2)
双指针逻辑分析：
1）什么时候使用双指针

• 有序的数组
• 遍历从数组中找到目标值

2）如果使用双指针：三数之和与两数之和的区别？

• 两数之和中：寻找的目标値是不变的，只有唯一一个，从最左边到最右边遍历就行

• 三数之和中：先令nums【0】为目标値，然后在nums【1】…nums【n-1】中遍历；
                        再令nums【1】为目标値，然后在nums【2】…nums【n-1】中遍历；…
  因此在三数之和中，需要使用for循环，控制目标值的变化，控制左指针的变化。

  重点： 三数之和的结果中，比如【1,0，-1】【2,1,1】【0，1，-1】 怎么实现去重呢。这里先将数组排序，然后存到set中，利用set实现去重，自己不去考虑，偷个懒。

这样实现去重的代价就是牺牲了大量的时间，毕竟set去重的原理是利用计算的hashcode判断目标是否一致。

/**
* 思路：比如【-4，-1，-1，0，1，2】，第一个-1成功匹配nums【2】和nums【5】后，
* 发现又要找-1的匹配，找两边必然结果重复，所以应该跳过第二个-1，直接找0
*/
#优化双指针去重
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List list = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {
            if(i>0 && nums[i]==nums[i-1]) continue;  //重点，实现跳过第二个-1
            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

            while (left < right) {
                int total = nums[left] + nums[right];
                if (total == target) {
                    list.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    //这两个while是搭配上面那个跳过-1的if语句，有时候我们发现单单if(i>0 && nums[i]==nums[i-1]) continue;满足不了所有场景跳过重复元素，比如案例[-2,0,0,2,2]，不写这两个while就不行
                     while (left < right) {
                        // 不管前后相不相等，left 都要往前走
                        left++;
                        if (nums[left - 1] != nums[left]) break;
                    }
                    while (left < right) {
                        // 不管前后相不相等，right 都要往后走
                        right--;
                        if (nums[right + 1] != nums[right]) break;
                    }
                   
                } else if (total < target) {
                    left++;
                } else
                    right--;
            }
        }

        return list;
    
    }
}

时间复杂度没变，但是速度立马提高