LeetCode 15. 三数之和

题目描述

LeetCode 15. 三数之和

解法一

首先普通方法暴力O(n3)肯定是TLE的，那么我们就应该想办法把复杂度给降下来。其实很快就可以想到利用哈希表来降复杂度。

我们先把nums数组进行排序，再利用HashMap将数组的值和对应的index存入map中。两层循环来遍历前两个数，利用map来查找第三个数即可(该数的值为-(nums[i]+nums[j]))，这样子复杂度就从O(n3)变成了O(n2)。

public class _15{
    static class Solution{
        public List<List<Integer>> threeSum(int[] nums){
            //利用Set来去重
            Set<List<Integer>> set =new HashSet<>();
            Map<Integer, Integer> map =new HashMap<>(nums.length);
            Arrays.sort(nums);
            for (int i =0; i < nums.length; i++) {
                map.put(nums[i], i);
            }
            for (int i =0; i < nums.length -2; i++) {
                for (int j = i +1; j < nums.length; j++) {
                    int t = -(nums[i] + nums[j]);
                    if(map.containsKey(t) && map.get(t) > j){
                        set.add(Arrays.asList(nums[i], nums[j], t));
                    }
              }
          }
          return new ArrayList<>(set);
}

解法二

我们可以不需要利用到哈希表。我们可以利用两个指针来找。head指针从i+1位开始往后查找，tail指针从nums.length-1位往前查找。当nums[head]+nums[tail]>-nums[i]时，说明tail指针指向的值太大，那么往前移动一位；当nums[head]+nums[tail]<-nums[i]时，说明head指针指向的值太小，需要往后移动一位；当相等时，则加入队列中。(注意：当找到的时候我们需要去重操作，避免加入重复的结果)

class Solution {
    public List<List<Integer>> threeSum(int[] nums){
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            int len = nums.length;
            for (int i = 0; i < len; i++) {
                //去重
                if(i > 0 && nums[i] == nums[i-1]){
                    continue;
                }
                int tmp = -nums[i];
                int head = i + 1;
                int tail = len - 1;
                while (head < tail){
                    if(nums[head] + nums[tail] > tmp){
                        --tail;
                    }else if(nums[head] + nums[tail] < tmp){
                        ++head;
                    }else {
                        res.add(Arrays.asList(nums[i], nums[head], nums[tail]));
                        //去重
                        while (head < tail && nums[tail] == nums[tail-1]){
                            --tail;
                        }
                         //去重
                        while (head < tail && nums[head] == nums[head+1]){
                            ++head;
                        }
                        if(head >= tail){
                            break;
                        }
                        ++head;
                        --tail;
                    }
                }
            }
            return res;
        }
}