2019.5.15

Title description:

Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts.

You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array.

Example:

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

Nums [0] + nums[1] = 2 + 7 = 9

Method 1: Violent 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++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j }; }}}throw new IllegalArgumentException("There are no two numbers.");
}
Copy the code

This solution is the most intuitive and simple, for each element in the array to look for a value that meets the target.

Complexity analysis

  • Time complexity:
  • Space complexity: Since no additional space is opened, its space complexity is.

Method 2, use HashMap

    public static int[] twoSum(int[] nums, int target) {
        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++) {
            int res = target - nums[i];

            If I =0, res=8, and the array does not contain this element, then get will be null
            if(map.containsKey(res) && map.get(res) ! = i) {return new int[]{i, map.get(res)}; }}throw new IllegalArgumentException("There are no two numbers.");
    }
Copy the code

Use HashMap to store the subscript corresponding to each array element, and then obtain the value required to add to target through the constant time query efficiency of HashMap. Compared with the above violent solution, the time required is greatly reduced.

You can also use the for loop only once

	public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int res = target - nums[i];
            if (map.containsKey(res)) {
                return new int[]{map.get(res), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("There are no two numbers.");
    }
Copy the code

Complexity analysis

  • Time complexity: due toHashMapThe time complexity of each query is, so only considerforThe influence of the cycle, so its time complexity is.
  • Space complexity: YesHashMapTo store the elements in the array, so the space complexity is $. O (N).