<Medium> 4Sum (LeetCode : C#)

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

📕 문제 설명

n개의 정수로 구성된 nums 배열이 주어질 때 다음을 만족하는 unique한 nums 리스트들을 반환

• 0 <= a, b, c, d < n
• a,b,c,d 모두 다른 값
• nums[a] + nums[b] + nums[c] + nums[d] = target

• Input
  정수 배열, target 값
• Output
  조건 만족하는 nums[a], nums[b], nums[c], nums[d] 리스트들

예제

풀이

포인터 2개로 두 값 고정해놓고 나머지 두개를 투 포인터로 또 각각 상황에 맞게 움직이면서 찾기

3sum이랑 접근이 똑같은데 정수 범위를 넘어가는 케이스 예외처리 해줘야 하는것이 있었다

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        
        List<IList<int>> answerList = new List<IList<int>>();
        Array.Sort(nums);
        if (nums[0] > 0 && target < 0) return answerList; // int 범위 벗어나는거 막고자 (제일 작은 수가 양순데 target 음수면 바로 return)

        for (int i = 0; i < nums.Length; i++) // 고정한 왼쪽 값
        {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            for (int j = i + 1; j < nums.Length; j++) // 고정한 오른쪽 값
            {
                if (j > i + 1 && nums[j] == nums[j-1]) continue;
                int curSum = nums[i] + nums[j];
                int left = j + 1; // 움직일 왼쪽 포인터
                int right = nums.Length - 1; // 움직일 오른쪽 포인터
                while (left < right)
                {
                    int totalSum = curSum + nums[left] + nums[right];
                    if (totalSum == target)
                    {
                        answerList.Add(new List<int>() {nums[i], nums[j], nums[left], nums[right]});
                        left++;
                        while (left < right && nums[left] == nums[left - 1])
                        {
                            left++;
                        }
                    }
                    else if (totalSum < target) // 현재 target 보다 작으므로 음수 절대값 낮추기
                    {
                        left++;
                    }
                    else // 현재 target 보다 크므로 양수 절대값 낮추기
                    {
                        right--;
                    }
                }
            }
        }

        return answerList;
    }
}

결과