문제

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

코드

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
  if (nums.size() < 3) return vector<vector<int>>();
  sort(nums.begin(), nums.end());

  vector<vector<int>> result;
  int before = 0;
  for (int i = 0; i < nums.size() - 2; i++) {
    int cur = nums[i];
    if (before == cur && i != 0) continue;
    int l = i + 1, r = nums.size() - 1;

    while (l < r) {
      int value = cur + nums[l] + nums[r];
      if (value == 0) {
        vector<int> tmp = { cur, nums[l], nums[r] };
        result.push_back(tmp);
        while (l < r && nums[r] == nums[r + 1]) r--;
        while (l < r && nums[l] == nums[l + 1]) l++;
        l++; r--;
      } else if (value < 0) {
        l++;
      } else {
        r--;
      }
    }
    before = cur;
  }
  return result;
}

풀이

i가 가리키는 것을 기준으로 두고, 왼쪽 포인터와 오른쪽 포인터를 이동해가며 nums[i]를 0으로 만들 수 있는 두 값을 찾는다.
nums 벡터의 크기가 3보다 작을때 null pointer exception이 발생해서 미리 결과 벡터를 생성자로 만들어서 리턴해야 한다.
또한, [-5, 0, 0, 5, 5] 같은 경우 [-5, 0, 5]를 찾은 후, l과 r을 l이 r보다 작은 범위 내에서 같은 것이 나오지 않을 때까지 이동한다.