Given an array of integers nums and a target value target, find the two integers in the array and return their array subscripts. You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.

1. Violence

Idea: Double loop through the number group

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j }; }}}throw new IllegalArgumentException("No two sum solution"); }}Copy the code

2. Hash twice

For the first time, all the values are stored in the hash table. For the second time, the values are directly compared

class Solution {
    public int[] twoSum(int[] nums, int target) {

        // Use hash table time complexity O (n)
        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++) {
            Integer position = target - nums[i];
            if(map.containsKey(position) && i ! = map.get(position)) {return new int[]{i,map.get(position)}; }}throw new RuntimeException("No legitimate data was found."); }}Copy the code

3. Hash again

When putting the data into the hash table, it checks whether the data matching the conditions exists in the hash table

class Solution {
    public int[] twoSum(int[] nums, int target) {

        // Use hash table time complexity O (n)
        Map<Integer,Integer> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            int position = target - nums[i];
            if (map.containsKey(position)){
                return new int[]{i,map.get(position)};
            }
            map.put(nums[i],i);
        }

        throw new RuntimeException("No legitimate data was found."); }}Copy the code