leetcode15：三数之和

题目链接

leetcode

题目描述

给一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" <<endl;
}

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
    两重枚举，无重复构造

    时间复杂度：O(n^2)
        其中 n 是数组的长度。
    空间复杂度：O(n^2)
        结果数组的大小为 n^2。
        排序算法的实现，通常为 O(logn)。
*/
class Solution_0 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }
            for (int j = i+1, k = nums.size()-1; j < k; j++) {
                if (j > i+1 && nums[j] == nums[j-1]) {
                    continue; // 去重
                }
                while (j < k-1 && nums[i] + nums[j] + nums[k-1] >= 0) {
                    k--; // 去重
                }
                if (nums[i] + nums[j] + nums[k] == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                }
            }
        }
        return res;
    }
};

/*
    思路同上，写法好理解

    时间复杂度：O(n^2)
    空间复杂度：O(logn)
*/
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }
            int j = i+1, k = nums.size()-1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                    while (j < k && nums[j] == nums[j+1]) {
                        j++; // 去重
                    }
                    while (j < k && nums[k] == nums[k-1]) {
                        k--; // 去重
                    }
                    j++, k--;
                } else if (sum < 0) {
                    j++;
                } else if (sum > 0) {
                    k--;
                }
            }
        }
        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> testCases = {
        {-1,0,1,2,-1,-4},
        {0,1,1},
        {0,0,0}
    };

    for (auto& nums : testCases) {
        cout << "Input: ";
        printArray(nums);
        vector<vector<int>> res = solution.threeSum(nums);
        cout << "Input: ";
        printArray(res);
    }
    
    return 0;
}

Golang 代码

package main

import (
	"fmt"
	"sort"
)

/*
   排序数组
   遍历数组：跳过重复元素，使用双指针在剩余部分寻找另外两个数，使其和为 0。

   时间复杂度：O(n^2)
       其中 n 是数组的长度。
       排序的时间复杂度为 O(nlogn)，遍历数组的时间复杂度为 O(n^2)。
   空间复杂度：O(logn)
       排序通常需要空间为 O(logn)，取决于排序算法的实现。
       因此，空间复杂度主要取决于排序算法的实现。
*/
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    n := len(nums)
    res := make([][]int, 0)

    for i := 0; i < n-2; i++ {
        // // 若当前数字大于 0，则三数之和一定大于 0，直接返回
        // if nums[i] > 0 {
        //     break
        // }
        // 若当前数字重复，则跳过
        if i > 0 && nums[i] == nums[i-1] {
            continue;
        }

        l, r := i+1, n-1
        for l < r {
            sum := nums[i] + nums[l] + nums[r]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[l], nums[r]})
                // 若当前数字重复，则跳过
                for l < r && nums[l] == nums[l+1] {
                    l++
                }
                // 若当前数字重复，则跳过
                for l < r && nums[r] == nums[r-1] {
                    r--
                }
                l++
                r--
            } else if sum < 0 {
                // 若三数之和小于 0，则右移
                l++
            } else if sum > 0 {
                // 若三数之和大于 0，则左移
                r--
            }
        }
    }
    return res
}

func main() {
	// 测试用例
	testCases := []struct {
		nums     []int
		expected [][]int
	}{
		{[]int{-1,0,1,2,-1,-4}, [][]int{{-1,-1,2}, {-1,0,1}}},
		{[]int{0,1,1}, [][]int{}},
		{[]int{0,0,0}, [][]int{{0,0,0}}},
	}

    for i, tc := range testCases {
		// 原始输入数据的备份
		fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
		result := threeSum(tc.nums)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}