leetcode-3sum

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/3sum/

　　4个数之和等于target，让你找出所有组合，注意输出的组合中不能有重复的

题目分析

　　对原数组进行排序，然后枚举第一个数，剩下的两个数采用双指针不断移动的思路，因此时间复杂度是O(n^2)，需要注意不要把重复的加进结果中，具体可以看代码中注释部分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
    private void build(int[] nums, int target) {
    	int len = nums.length;
    	for (int i = 0; i <= len - 3; i++) {
    		if (i > 0 && nums[i] == nums[i - 1]) { // 重复的i不加
    			continue;
    		}
    		int first = i + 1;
    		int last = len - 1;
    		while (first < last) {
    			int sum = nums[i] + nums[first] + nums[last];
    			if (sum < target) {
    				first++;
    			} else if(sum > target) {
    				last--;
    			} else {
    				List<Integer> tmp = new ArrayList<Integer>();
    				tmp.add(nums[i]);
    				tmp.add(nums[first]);
    				tmp.add(nums[last]);
    				ans.add(tmp);
    				first++;
    				last--;
                    // 以下代码段是两个指针不断移动的过程，是为了避免跟上次指针指向的值相同
    				while (first < last && nums[first] == nums[first - 1]) {
    				    first++;
    				}
    				while (first < last && nums[last] == nums[last + 1]) {
    				    last--;
    				}
    			}
    		}
    	}
    }
    public List<List<Integer>> threeSum(int[] nums) {
        ans.clear();
        Arrays.sort(nums);
        build(nums, 0);
        return ans;
    }
}

　　算法复杂度：O(n^2)