[leetcode] TwoSum

spark805·2021년 10월 16일
0

leetcode

목록 보기
1/9

주어진 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;
    }
profile
성장 지향 백엔드 개발자

0개의 댓글