3Sum

vector<vector<int>> threeSum(vector<int>& nums) { set<vector<int>> t; vector<vector<int>> res = {}; sort(nums.begin(), nums.end()); if(nums.size() < 3){ return res; } for (int i = 0; i < nums.size() - 2; i++) { if (i != 0 && nums[i] == nums[i - 1]) continue; int left = i + 1, right = nums.size() - 1; while (left != right) { if (nums[i] + nums[left] + nums[right] == 0) { vector<int> v = { nums[i], nums[left], nums[right] }; t.insert(v); left++; } else if (nums[i] + nums[left] + nums[right] > 0) { right--; } else { left++; } } } for (set<vector<int>>::iterator it = t.begin(); it != t.end(); it++) { res.push_back(*it); } return res; }

리스트 내에서 합이 0이 되는 모든 경우를 찾는다.

우선 리스트를 오름차순으로 정렬한다.

기준 인덱스는 0에서 순서대로 증가, 남은 구역의 양 끝에서 좁혀오면서 탐색한다.

리스트가 정렬되어 있으므로 세 숫자의 합이 0보다 크면 남은 구역의 오른쪽 인덱스를, 0보다 작으면 왼쪽 인덱스를 이동시킨다.