cpp-flashcards/org/study_deck_02/dsa/arrays-hashing/0001-two-sum.org

#+ANKI_DECK: study_deck_02
* TODO 0001. Two Sum :easy:
:PROPERTIES:
:NEETCODE: [[file:../../roadmap.org::*0001. Two Sum][0001. Two Sum]]
:END:

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:*


#+begin_src
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
#+end_src


*Example 2:*


#+begin_src
Input: nums = [3,2,4], target = 6
Output: [1,2]
#+end_src


*Example 3:*


#+begin_src
Input: nums = [3,3], target = 6
Output: [0,1]
#+end_src


*Constraints:*

 - ~2 <= nums.length <= 10^{4}~

 - ~-10^{9} <= nums[i] <= 10^{9}~

 - ~-10^{9} <= target <= 10^{9}~

 - *Only one valid answer exists.*

*Follow-up: *Can you come up with an algorithm that is less than ~O(n^{2})~ time complexity?

** TODO Approach
Write your approach here.

** TODO Python
#+begin_src python :lc-problem 1 :lc-lang python3
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sb = {}
        for xi, x in enumerate(nums):
            want = target - x;
            if want in sb:
                return sb[want], xi
            sb[x] = xi
#+end_src

** TODO C++
#+begin_src cpp :lc-problem 1
#include <algorithm>
class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
    std::sort(nums.begin(), nums.end());
    for (int i=0; i< nums.size(); i++) {
      int x = nums[i];
      if (x > target) {
        return {};
      }
      // TODO: c++ binary search, i forgot how to do this
      int want = target - x
      auto it = std::binary_learch(nums.begin() + i + 1, nums.end(), want);
      if (it != nums.end() && *it == want) {
        int wi = std::distance(nums.begin(), it)
        return {i, wi}
      }
    }
    reuturn {};
  }
};
#+end_src

#+RESULTS: