LeetCode 题解-18. 4Sum - 张磊的技术笔记

对Leetcode 18. 4Sum 题目的求解。

Problem Description#

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

The solution set must not contain duplicate triplets.

Example 1#

1
Given array nums = [-1, 0, 1, 2, -1, -4],
2

3
A solution set is:
4
[
5
  [-1, 0, 1],
6
  [-1, -1, 2]
7
]

Analysis#

这是一道two-pointer的题目．通过O(n)的遍历将自由度为3的搜索题目降到自由度为2.由此我们可以转化为2sum的问题．至于如何解决2sum的问题，我们首先进行排序，再使用two pointer进行搜索，总的复杂度为O(n^2).

Solution#

1
class Solution {
2
    public static List<List<Integer>> threeSum(int[] nums) {
3
        Arrays.sort(nums);
4
        List<List<Integer>> res = new LinkedList<>();
5
        int s = 0;
6
        int t = 0;
7
        for (int i = 0; i < nums.length - 2; ++i){
8
            if (i > 0 && nums[i] == nums[i-1]) continue;
9
            s = i + 1;
10
            t = nums.length - 1;
11
            while ( s < t){
12
                if (s > i+1 && t < nums.length - 1 && nums[s] == nums[s-1] && nums[t] == nums[t+1]){
13
                    s ++;
14
                    t --;
15
                    continue;
16
                }
17
                if (nums[s] + nums[t] == - nums[i]){
18
                    LinkedList<Integer> l = new LinkedList<>();
19
                    l.add(nums[i]);
20
                    l.add(nums[s]);
21
                    l.add(nums[t]);
22
                    res.add(l);
23
                    s ++;
24
                    t --;
25
                }
26
                else if (nums[s] + nums[t] > - nums[i]) t --;
27
                else s ++;
28
            }
29
        }
30
        return res;
31
    }
32
}