龙

哇咔咔

0%

LeetCode 15.3Sum

发表于 更新于 分类于 Disqus：
求三个数的和。

15.3Sum

Description:

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

Note: The solution set must not contain duplicate triplets.

题目理解：输入一个数组和一个目标值，求3个数之和等于目标值。返回所有这些3个数的组合，但是不能有重复的组合。

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
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int target = 0, m = nums.length;
        for ( int i = 0, bound = m - 2 ; i < bound && nums[i] <= target ; ) {
            int l = i + 1, r = m - 1, sum = target - nums[i];
            while ( l < r ) {
                int temp_sum = nums[l] + nums[r];
                if ( temp_sum < sum ) l++; 
                else if ( temp_sum > sum ) r--; 
                else {
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[l]);
                    item.add(nums[r]);
                    result.add(item);
                    l++;
                    while ( l < r && nums[l] == nums[l-1] ) l++;
                    r--;
                    while ( l < r && nums[r] == nums[r+1] ) r--;
                } 
            }
            i++;
            while ( i < bound && nums[i] == nums[i-1] ) i++;
        }
        return result;
  }     
}

首先将数组进行排序，外层循环从左向右，内部就是一个Two_Sum，这里注意要跳过重复的值。

复杂度n^2，运行时间69ms。

images