[LeetCode] 1. Two Sum (코딩테스트, 릿코드, tech interview)

릿코드 하나씩 공부하면서 열심히 풀기로

1, 2, 3 세번에 걸쳐서 퍼포먼스를 올렸고, 거의 최대치로 나옴

• Process
  // 1. Input
  // 2. Iterate all with hashmap (i)
  // 2.1. Check target-nums[i]
  // 2.1.1. If so -> return answer
  // 3. Finish

package algorithm_sites.leetcode;

import java.util.*;

public class LC_00001_TowSum {

    public int[] twoSum_1(int[] nums, int target) {
        if (nums.length == 2) {
            return new int[] {0,1};
        }

        for (int i = 0; i < nums.length-1; ++i) {
            for (int j = i+1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }

        return null;
    }

    public int[] twoSum_2(int[] nums, int target) {
        if (nums.length == 2) {
            return new int[] {0,1};
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target-nums[i])) {
                if (map.get(target-nums[i]) != i) {
                    return new int[] {map.get(target-nums[i]), i};
                }
            }
        }

        return null;
    }

    public int[] twoSum_3(int[] nums, int target) {
        if (nums.length == 2) {
            return new int[] {0,1};
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(target-nums[i])) {
                return new int[] {map.get(target-nums[i]), i};
            }
            map.put(nums[i], i);
        }

        return null;
    }

    public static void main(String args[]) {
        LC_00001_TowSum lc = new LC_00001_TowSum();

        int[] result = lc.twoSum_3(new int[]{3, 2, 4}, 6);

        for (int i = 0; i < result.length; ++i) {
            System.out.print(result[i] + " ");
        }
    }

}

 

 

2021.08.06 - [Algorithm] - [Codility] MaxNonoverlappingSegments, 코딜리티 그리디 greedy

[Codility] MaxNonoverlappingSegments, 코딜리티 그리디 greedy