Leetcode 18. 4Sum

4Sum:

給定一個整數陣列，找出由四個數加總為 0 的所有組合

Python

• 排序陣列
• for 迴圈兩層，要找到解的其中兩個數值
• 設定左端點和右端點
  • 加總值 > 0：將右端點向左移動，找到更小的加總值
  • 加總值 < 0：將左端點向右移動，找到更大的加總值
  • 加總值等於 0：即為答案之一，若過去沒有找過這個組合的答案，即紀錄起來

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        
        results = []
        nums = sorted(nums)
        
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                left = j + 1
                right = len(nums) - 1
                temp_target = target - nums[i] - nums[j]
                
                while left < right:
                    sum = nums[left] + nums[right]
                    if sum == temp_target:
                        result = [nums[i], nums[j], nums[left], nums[right]]
                        if result not in results:
                            results.append(result)
                        
                        left += 1
                        right -= 1
                    
                    elif sum < temp_target:
                        left += 1
                    elif sum > temp_target:
                        right -= 1
        
        return results

C++

跟Python解一樣

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {

        vector<vector<int>> results;
        sort(nums.begin(), nums.end());
        
        for (int i=0; i<nums.size(); i++) {
            for (int j=i+1; j<nums.size(); j++) {
                int left = j+1;
                int right = nums.size()-1;
                int temp_target = target - nums[i] - nums[j];
                
                while (left < right) {
                    int lr_sum = nums[left] + nums[right];
                    
                    if (lr_sum == temp_target) {
                        vector<int> result = {nums[i], nums[j], nums[left], nums[right]};
                        
                        if (find(results.begin(), results.end(), result) == results.end()) {
                            results.push_back(result);
                        }
                        left++;
                        right--;
                    }   
                    else if (lr_sum < temp_target) {
                        left++;
                    }
                    else if (lr_sum > temp_target) {
                        right--;
                    }
                }
            }
        }
        
        return results;
    }
};