주어진 array nums 중 두 수를 더하였을 때 주어진 정수 target에 대해서 구할 수 있다고 가정한다.
이때 array nums에서 target을 구하기 위해 필요한 두 숫자의 index를 리턴해야한다.
먼저 Array를 정렬한 후 while문을 돌면서 투포인터 형태로 left 인덱스, right 인덱스를 구하는 방식으로 풀이를 하였다.
public int[] twoSum(int[] nums, int target) {
int left=0;
int right = nums.length-1;
int sum = target-1;
// 원래의 순서를 알기 위한 목적의 list
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
// sorting
Arrays.sort(nums);
while(left <=right) {
sum = nums[left]+nums[right];
//target 넘버를 찾으면 break;
if(sum==target && left!=right) {
break;
}
// 두 수를 더한 값이 target보다 작고, left가 right보다 작을때 left 인덱스 증가
if(sum<target && left < right) {
left++;
// 두 수를 더한 값이 target보다 크고, left가 right보다 클 때 right 인덱스 감소
} else if(sum > target && right > left) {
right--;
//left==right 인 경우 처리
} else if (sum <= target && left ==right) {
right++;
} else if(sum >= target && right == left) {
left--;
}
}
//left의 실제 인덱스, right의 실제 인덱스 get
int leftIndex = list.indexOf(Integer.valueOf(nums[left]));
int rightIndex = list.indexOf(Integer.valueOf(nums[right]));
// 같은 숫자가 있는 경우 인덱스 조정 처리
if(nums[left]==nums[right]) {
list.remove(leftIndex);
rightIndex = list.indexOf(Integer.valueOf(nums[right])) + 1;
}
int[] result = {leftIndex, rightIndex};
Arrays.sort(result);
return result;
}
실제 다른 사람의 Solution과 비교하였을 때에 코드가 장황한 편...
아래는 풀이 중 가장 심플한 풀이로, 코드를 효율적으로 짜는 방법에 대해 고민을 다시 해보게 되었다.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
int compliment = target - nums[i];
if(map.containsKey(compliment)) {
return new int[] {map.get(compliment), i};
} else {
map.put(nums[i], i);
}
}
return null;
}