[LeetCode] 15. 3Sum

[Medium] 11. Container With Most Water

https://leetcode.com/problems/3sum/

Example

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

문제 설명

n개의 원소가 들어가 있는 배열이 들어 올 경우, 3개의 원소의 합 (a, b, c)이 0이 되는 조합들을 찾아 리턴한다.

나의 풀이

O(N)

1. X,Y,Z 세 개의 포인트를 둔다.
2. X를 고정한 후, 11번 문제과 동일하게 2 point 접근을 수행한다.
3. Y+Z == -X일 경우, 해당 원소를 리스트에 집어넣는다.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0; i < nums.length-2; i++){
            if(i > 0 && nums[i] == nums[i-1]){
                continue;
            }
            int x = nums[i];
            int y_idx = i+1;
            int z_idx = nums.length - 1;
            while(y_idx < z_idx){
                if(nums[y_idx] + nums[z_idx] == -x){
                    res.add(Arrays.asList(x, nums[y_idx], nums[z_idx]));
                    y_idx++;
                    z_idx--;
                    while((y_idx < z_idx) && (nums[y_idx] == nums[y_idx-1])) y_idx++;
                    while((y_idx < z_idx) && nums[z_idx] == nums[z_idx+1]) z_idx--;
                }else if(nums[y_idx] + nums[z_idx] > -x){
                    z_idx--;
                }else{
                    y_idx++;
                }
            }
        }
        return res;
    }
}