DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

Cover image for LeetCode's Two Sum Solution - Java
Piyush Acharya
Piyush Acharya

Posted on • Updated on

LeetCode's Two Sum Solution - Java

Two Sum

Intuition

I first considered how I would go about searching for two numbers that equaled the target number. My initial thought was to loop through the list, looking for numbers 'n-1' and 'n+1' away from the current number. However, I soon realized that the two numbers that add up to target could be anywhere on the list.

Approach

I first loop through all of the numbers in the list that was entered, and then I loop through the list again, beginning with `i + 1'. This is because if you start at 0, it will look at the same element twice, and if that number added to itself is target, it will be counted twice. If I come across two numbers that are equal to target, I add them to a list and return them. Otherwise, I return an empty list.

Complexity

  • Time complexity: O(n^2)

Code

GitHub: https://github.com/Verisimilitude11/LeetCode-Problems/tree/main/1.%20Two%20Sum

java
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
int num1 = nums[i];
for (int j = i + 1; j < nums.length; j++) {
int num2 = nums[j];
if (num1 + num2 == target) {
int[] output = {i, j};
return output;
}
}
}
int[] output = {};
return output;
}
}

Top comments (2)

Collapse
 
pinich profile image
Pini Cheyni

You can use hash-map (Dictionary) to reduce your time complexity!
You need look for the result of the sum - a[x] in the dictionary, if it exists then return true otherwise add this value to the dictionary and move to the next element (a[x+1])

Collapse
 
verisimilitude11 profile image
Piyush Acharya

Yes, thanks for the feedback! I implemented it in a newer version of code: github.com/Verisimilitude11/LeetCo...

Timeless DEV post...

Git Concepts I Wish I Knew Years Ago