1. Two Sum (Easy)

https://leetcode.com/problems/two-sum/

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

 

Solutions

class Solution {

    // Returned values are index of target element, we are required to keep track of the index for each element before
    // sorting the nums. Besides, given nums could contain duplicates, so use the Queue to keep the element index.
    Map<Integer, Queue<Integer>> map = new HashMap<>();

    public int[] twoSum(int[] nums, int target) {
        int[] ans = {0, 0};
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayDeque<>());
            }

            map.get(nums[i]).add(i);
        }

        Arrays.sort(nums);

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

            if (nums[i] + nums[j] > target) {
                j--;
            }

            if (nums[i] + nums[j] == target) {
                // Poll it out of the Queue after use just in case the same element appears twice.
                ans[0] = map.get(nums[i]).poll();
                ans[1] = map.get(nums[j]).poll();

                break;
            }
        }

        Arrays.sort(ans);

        return ans;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-24 22:41:40

results matching ""

    No results matching ""