[1] Two Sum
https://leetcode.com/problems/two-sum/description/
- algorithms
- Easy (46.37%)
- Likes: 19171
- Dislikes: 682
- Total Accepted: 3.8M
- Total Submissions: 8.3M
- Testcase Example: ‘[2,7,11,15]\n9’
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] Output: 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 <= 103
-109 <= nums[i] <= 109
-109 <= target <= 109
- Only one valid answer exists.
Approach 1: Brute Force
Loop through each element x
and find if there is another value that equals to target - x
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> answer;
int i, j;
for(i = 0; i< nums.size() - 1; i++){
for(j = i + 1; j < nums.size(); j++){
int diff = target - nums[j];
if(nums[i] == diff){
answer.push_back(i);
answer.push_back(j);
}
}
}
return answer;
}
};
Complexity Analysis
- Time Complexity: $O(n^2)$
- Space Complexity: $O(1)$