I'm working on the Leetcode's Two Sum problem.

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].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

My solution:

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  ) {
                if(nums[i] == target - nums[j]) {  //Here
                    return new int[] {i,j};
                }
            }
        }
        return null;
    }
}

The runtime of the code reduced to half just by replacing nums[i] nums[j] == target with nums[i] == target - nums[j]

It is my first leetcode problem I and here am already learning new stuff. I would appreciate it if you would give some tips on how to find time-efficient methods.

CodePudding user response：

The runtime of the code reduced to half

The change you've made should not have any considerable performance impact. Because some of the test cases are based on randomly generated data, even the same code might behave differently because the input not the same. And there are other factors that you can't control and which can affect performance significantly, like garbage collection.

Therefore, execution time (on a local machine or on a remote server) is not a precise measurement. You might encounter situations borderline situations when your code would be rejected due to timeout, but the next attempt to submit the same code would succeed.

Now regarding improvement you apply in this case.

To begin with, your current code is based on brute-force approach (which always means worst possible performance) and it has quadratic time complexity O(n^2).

There's a couple of more performant alternatives.

You can sort the array and then apply the so-called two-pointer approach, i.e. define two variables: one pointing to the start of the array (the smallest element), another pointing to the very end of the array (the largest value), and the move these indices towards each other comparing the sum of elements with the target. This algorithm would have time complexity of O(n log n) because of sorting and space complexity O(1).

Another approach would be to use a HashMap and store the index of each encountered element as a value, and it's a counter-part number as a key (i.e. inverted value = target - currentNumber). And when we hit an array element which is already present in the Map as a key it would mean that its counter-part also exist. That means we found the pair of elements that form the target number.

The time complexity of this algorithm is linear O(n), which is pretty fast, but it has a space complexity of O(n) because we need to maintain a map.

That's how it might be implemented:

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numberIndexByCounterPart = new HashMap<>();
    for (int i = 0; i < nums.length; i  ) {
        int next = nums[i];
        Integer index = numberIndexByCounterPart.get(next);
        if (index != null) {
            return new int[]{index, i};
        }
        numberIndexByCounterPart.put(target - next, i);
    }
    return null;
}

CodePudding user response：

the difference between this the plus sign and I think actually plus sign is the method that usually get to numbers and returns some of this numbers and probably it works slow than minus