#LeetCode:15. 3Sum

灆洢 2018-10-05 01:38:47

先將陣列排序,之後三個數字先巡覽陣列去固定一個數字後,接著另外兩個數字從兩端向內夾出來即可。在巡覽陣列的時候和夾最後兩個解的時候如遇到重複的數字記得略過。

C++(84ms)

/*******************************************************/
/* LeetCode 15. 3Sum                                   */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/05                                 */
/*******************************************************/
class Solution {
public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    if(nums.size() < 3) return result;

    sort(nums.begin(), nums.end());

    /* i + j + k = 0 => j + k = -i */
    for(int i = 0 ; i < nums.size() - 2 ; ++i){
      if(i == 0 || nums[i] != nums[i-1]){
        int finalSum = -nums[i];
        for(int j = i+1, k = nums.size() - 1 ; j < k ; ){
          int currentSum = nums[j] + nums[k];
          if( currentSum > finalSum ){
             do { --k; } while(j < k && nums[k] == nums[k+1]);
          }
          else if(currentSum < finalSum){
            do { ++j; } while(j < k && nums[j] == nums[j-1]);
          }
          else{
            result.push_back({nums[i], nums[j], nums[k]});

            do { ++j; } while(j < k && nums[j] == nums[j-1]);
            do { --k; } while(j < k && nums[k] == nums[k+1]);
          }
        }
      }
    }

    return result;
  }
};

在〈“#LeetCode:15. 3Sum”〉中有 2 則留言

  1. […] 15. 3Sum 擴張到 4Sum 或是 nSum 也是一樣的道理,先排序後定住 n-2 […]

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料