leetcode-15-3Sum

发表于   |  

描述

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:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

分析

思路：先给数组排序，按从左至右从小到大得顺序排列，通过第一层循环确定第一个数，其他两个在第一个数的右边（都比第一个数大）取，两个数从两侧向中间靠拢，如果三数相加大于0，第三个数向左移动（减小），三数相加小于0，第二个数向右移动。跳过相同的数字。时间复杂度$O(n^2)$，空间复杂度是$O(1)$

解决方案1(Python)

思路和C++的版本是一样的

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
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = []
    
        for i in range(len(nums)-2):
            if i==0 or i != 0 and nums[i-1]!=nums[i]:
                left = i + 1
                right = len(nums) - 1
                while left < right:
                    s = nums[i] + nums[left] + nums[right]
                    if s == 0:
                        result.append([nums[i], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        while left < right and nums[left] == nums[left-1]:
                            left += 1
                        while left < right and nums[right] == nums[right+1]:
                            right -= 1
                    elif s > 0:
                        right -= 1
                    else:
                        left += 1
        return result

解决方案2(C++)

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
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
    
        int size = nums.size();
        sort(nums.begin(), nums.end());
    
        for(int i = 0; i < size; i++) {
            while(i > 0 && i < size && nums[i] == nums[i-1]) {
                i++;
            }
    
            int j = i + 1;
            int k = size-1;
    
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0) {
                    vector<int> now(3);
                    now[0] = nums[i];
                    now[1] = nums[j];
                    now[2] = nums[k];
    
                    result.push_back(now);
                    j++;
                    k--;
                    while(j < k && nums[j] == nums[j-1]) {
                        j++;
                    }
                    while(j < k && nums[k] == nums[k+1]) {
                        k--;
                    }
                }else if(sum > 0){
                    k--;
                }else {
                    j++;
                }
            }
    
        }
        return result;
    }
};

解决方案3(Rust)

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
pub struct Solution {}

impl Solution {
    pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let len = nums.len();
        if len < 3 {
            return vec![]
        }
        let mut nums = nums;
        nums.sort();
        let mut i = 0;
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut previous = nums[0] - 1;
        while i < len - 2 {
            if nums[i] == previous {
                i += 1;
                continue;
            }
            previous = nums[i];
            let vec = Solution::two_sum(&nums[(i+1)..len], 0 - nums[i]);
            for t in vec.iter() {
                result.push(vec![nums[i], t.0, t.1]);
            }
            i += 1;
        }
        result
    }

    #[inline(always)]
    fn two_sum(nums: &[i32], sum: i32) -> Vec<(i32, i32)> {
        let (mut i, mut j) = (0_usize, nums.len() - 1);
        let mut result = Vec::new();
        while i < j {
            if nums[i] + nums[j] < sum {
                i += 1;
            } else if nums[i] + nums[j] > sum {
                j -= 1
            } else {
                result.push((nums[i], nums[j]));
                i = Solution::next_unique(nums, i, true);
                j = Solution::next_unique(nums, j, false);
            }
        }
        result
    }

    #[inline(always)]
    fn next_unique(nums: &[i32], idx: usize, forward: bool) -> usize {
        let current = nums[idx];
        let mut i = idx;
        while i > 0 && i < nums.len() && nums[i] == current {
            i = if forward { i + 1 } else { i - 1 }
        }
        i
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_leetcode_15() {
        assert_eq!(Solution::three_sum(vec![-1, 0, 1, 2, -1, -4]), vec![vec![-1, -1, 2], vec![-1, 0, 1]]);
        let empty_vec: Vec<Vec<i32>> = vec![];
        assert_eq!(Solution::three_sum(vec![]), empty_vec);
    }
}

解决方案4（Golang）

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
func threeSum(nums []int) [][]int {
    if len(nums) < 3 {
        return nil
    }
    
    sort.Ints(nums)
    length := len(nums)
    
    var result [][]int
    for i := 0; i < length - 2; i++ {
        if nums[i] > 0 {
            break
        }
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        left := i+1
        right := length-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum > 0 {
                for right=right-1; left < right && nums[right] == nums[right+1]; right-- {}
            } else if sum < 0 {
                for left=left+1; left < right && nums[left] == nums[left-1]; left++ {}
            } else {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                for left=left+1; left < right && nums[left] == nums[left-1]; left++ {}
                for right=right-1; left < right && nums[right] == nums[right+1]; right-- {}
            }
        }
    }
    return result
}

相关问题

题目来源