Решения для проблемы LeetCode «две суммы» в Java

Проблема с Leetcode:- https://leetcode.com/problems/two-sum/

Давайте разберемся в проблеме.

Здесь мы должны найти индексы двух чисел из заданного массива, в которых сумма этих двух чисел должна быть равна целевому числу, указанному в аргументе функции.

Здесь, подумал я, самое простое решение — просто найти числа, сумма которых равна целевому числу. Итак, первое, что пришло мне в голову:

целевое число = первое число + второе число

но здесь проблема в том, что числа могут быть из любых индексов. Итак, вторая мысль, которая пришла мне в голову:

целевой номер = массив[i] + массив[j]

class Solution {
    public int[] twoSum(int[] nums, int target) {
         
        
        for(int i=0;i<nums.length;i++)
        {
            for(int j=0;j<nums.length;j++)
            {
            
                if(i == j)
                {
                    break; 
                }
              
                if(nums[i] + nums[j] == target)
                {
                    return new int[] {i,j};
                }
            }    
        }
        return new int[] {0,0};    
    }
}

Здесь моя простая логика такова: если мы получили i == j (то же значение), то просто разорвем этот цикл. И оставшийся элемент должен идти в соответствии с нашей логикой (цель = массив [i] + массив [j]) и возвращать два индекса, которые соответствуют нашей логике.

Но здесь проблема в том, что сложность этой программы составляет O(n²). Нам нужно уменьшить эту сложность.

Итак, я использовал Hashmap, чтобы уменьшить сложность.

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

Вот производительность второго кода.

Нажмите один раз, если вам нравится мой подход к решению и решение.

Спасибо за терпеливое чтение!!!