Leetcode 1: Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution:

1. Brute Force

   a. This is the solution of my first reaction , Conventional loop ergodic addition

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ans = new int[2];
        for (int i = 0; i <= nums.length - 2; ++i) {
            for (int j = i + 1; j <= nums.length - 1; ++j) {
                if (nums[i] + nums[j] == target) {
                    ans[0] = i;
                    ans[1] = j;
                    return ans;
                }
            }
        }
        throw new IllegalArgumentException("no match found");
    }
}

  b. This violent search method is subtraction , It is easier to extend the following HashMap Solution method

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                int complement = target - nums[i];
                if (nums[j] == complement) {
                    return new int[] {i, j};
                }
            }
        }
        throw new IllegalArgumentException("no match found");
    }
}

2.  HashMap

HashMap Storage nums The value of array and the key value pair of subscript , Return if found , Deposit if not found HashMap

The time complexity of this solution is O(n)

Be careful ,HashMap containsKey The time complexity of the method is O(1),containsValue The time complexity of the method is O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("no match found");
    }
}