[leetcode] 4Sum(Foursum)

---

Leetcode 4Sum

내가 생각한 방식은 배열을 정렬하고 left와 right로 양쪽 끝을 잡고 leftSub와 rightSub로 target 값에 근접하도록 하는 것이다.
이 후 leftSub와 rigthSub에서 양쪽 끝을 제외한 내부를 체크한다.
left + right 값이 target 보다 크면 right–; left + right 값이 target 보다 작으면 left++;을 적용한다.
다만 아래의 코드로는 중복문제를 해결하지 못하였다.

public List<List<Integer>> fourSum(int[] nums, int target) {
		List<List<Integer>> answer = new LinkedList<List<Integer>>();
		int left = 0;
		int right = nums.length - 1;
		int originTarget = target;
		int leftSub;
		int rightSub;

		Arrays.sort(nums);

		while (right - left > 2) {
			leftSub = left + 1;
			rightSub = right - 1;
			target = originTarget - nums[left] - nums[right];

			while (leftSub < rightSub) {
				List<Integer> temp = new LinkedList<Integer>();
				if (nums[leftSub] + nums[rightSub] == target) {
					temp.add(nums[left]);
					temp.add(nums[leftSub]);
					temp.add(nums[right]);
					temp.add(nums[rightSub]);
					answer.add(temp);
					leftSub++;
					rightSub--;
				} 
				else if (nums[leftSub] + nums[rightSub] < target) {
					leftSub++;
				} 
				else if (nums[leftSub] + nums[rightSub] > target) {
					rightSub--;
				}
			}
			
			if(nums[left] + nums[right] <= originTarget) {
				left++;
			}
			else if(nums[left] + nums[right] > originTarget) {
				right--;
			}
		}

		return answer;
	}

그래서 다시 중복을 해결 할 수 있는 코드를 생각해보자.