1. Sum of two numbers

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

This is the first time I’ve seen a solution to this problem

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,List<Integer>> map = new HashMap<>();
        for(int i=0; i<nums.length; I++){// the first elementfor(int j=nums.length-1; j>0; Int key = nums[I] + nums[j]; List<Integer> value = new ArrayList<>(); value.add(i); value.add(j); map.put(key,value); } } List<Integer> list = map.get(target); Integer[] arr = new Integer[list.size()]; //Integer cannot directly convert int array list.toarray (arr); Int [] result = new int[arr.length];for (int i = 0; i < arr.length; i++) {
			result[i] = arr[i];
		}
        returnresult; }}Copy the code

Although it is just a simple small problem, but the solution is also a little too troublesome to optimize

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        int m = 0;
        int n = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    m = i;
                    n = j;
                    break;
                } else {
                    continue;
                }
            }
        }
        result[0] = m;
        result[1] = n;
        returnresult; }}Copy the code

There are no utility classes using Java

All of the above solutions require two iterations of order n^2 time.

Take a look at the answers provided on the official website and you only need to iterate once to get the results.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){ int comple = target - nums[i];if(map.containsKey(comple)){
                return new int[] {map.get(comple),i};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution"); }}Copy the code

Time is order n.