You are 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.
\n\nYou can return the answer in any order.
\n\n\n
Example 1:
\n\n\nInput: nums = [2,7,11,15], target = 9\nOutput: [0,1]\nExplanation: Because nums[0] + nums[1] == 9, we return [0, 1].\n\n\n
Example 2:
\n\n\nInput: nums = [3,2,4], target = 6\nOutput: [1,2]\n\n\n
Example 3:
\n\n\nInput: nums = [3,3], target = 6\nOutput: [0,1]\n\n\n
\n
Constraints:
\n\n2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109\nFollow-up: Can you come up with an algorithm that is less than
O(n2) time complexity?"},"approach":{"insight":"A hash map gives each complement lookup in constant time.","steps":["Make an empty map from value to index.","For each index `i`, find `target - nums[i]` in the map.","If the map has it, return both indices.","Else, put `nums[i]` in the map with index `i`."],"time":"O(n)","space":"O(n)","hints":["For each number, the partner value `target - x` is fixed, so ask whether that partner appeared earlier."]},"state":null,"note":null},"remaining":793,"topics":["Array","String","Hash Table","Math","Dynamic Programming","Sorting","Greedy","Depth-First Search","Binary Search","Matrix","Breadth-First Search","Tree","Two Pointers","Bit Manipulation","Prefix Sum","Heap (Priority Queue)","Simulation","Binary Tree","Stack","Database","Graph Theory","Counting","Sliding Window","Design","Enumeration","Backtracking","Union-Find","Linked List","Number Theory","Ordered Set","Monotonic Stack","Segment Tree","Divide and Conquer","Recursion","Trie","Queue","Combinatorics","Binary Search Tree","Bitmask","Geometry","Memoization","Topological Sort","Hash Function","Binary Indexed Tree","Shortest Path","JavaScript","String Matching","DP on Trees","Game Theory","Interactive","Data Stream","Rolling Hash","Greatest Common Divisor","Euclidean Algorithm","Directed Acyclic Graph","Monotonic Queue","Dijkstra's Algorithm","Bracket Sequences","Brainteaser","Minimax","Knapsack Problem","Doubly-Linked List","Merge Sort","Binary Lifting","Prime Factorization","Randomized","Zero-Sum Game","Z Algorithm","Lowest Common Ancestor","Knuth–Morris–Pratt Algorithm","Iterator","Counting Sort","Longest Increasing Subsequence","Fermat's Little Theorem","Pandas","Sweep Line","0-1 Knapsack","Bipartite Graph","Bidirectional Search","Primality Test","Sieve Theory","Quickselect","Flow Network","Concurrency","Quicksort","Floyd's Cycle Finding Algorithm","Bucket Sort","Treap","Polygons","Longest Common Subsequence","Suffix Array","Minimum Spanning Tree","Boyer–Moore String-Search Algorithm","Pigeonhole Principle","Prime Number Sieve","Complete Knapsack","A* Search","Heuristic Search","Cartesian Tree","Graph Coloring","Least Common Multiple","Matching (Graph)","Bubble Sort","Shell","Impartial Game","Sqrt Decomposition","Reservoir Sampling","Probability and Statistics","Aho–Corasick Algorithm","Kosaraju's Algorithm","Tarjan's SCC Algorithm","Meet in the Middle","Successive Shortest Path Algorithm","Suffix Automaton","Suffix Tree","Algorithm X","Radix Sort","Boyer–Moore Majority Vote Algorithm","Nim Game","Linear Algebra","Eulerian Circuit","Eulerian Path","Inclusion-Exclusion Principle","Hungarian Algorithm","Minimum-Cost Flow","Prim's Algorithm","Kruskal's Algorithm","Borůvka's Algorithm","Edmonds–Karp Algorithm","MPM Algorithm","Push-Relabel Algorithm","Dinic's Algorithm","Manacher","Range Minimum/Maximum Query","Brute-Force Search","Sprague–Grundy Theorem","Semi-Eulerian Graph","Bézout's Lemma","Extended Euclidean Algorithm","Bellman–Ford Algorithm","Floyd–Warshall Algorithm","Rejection Sampling","Closest Pair of Points","Ternary Search","Hamiltonian Path","Maximum Flow","Maximum Matching","0-1 BFS","Strongly Connected Component","Tournament Sort","Dancing Links","Newton's Method","Euler's Totient Function","Euler's Theorem","Convex Hull","Eulerian Graph","Timsort","Lexicographically Minimal String Rotation","Planar Graph","K-D Tree","Triangulation","Persistent Data Structure","Lyndon Factorization","Biconnected Component","Bridge (Graph)","Minimum Cut","Articulation Point","Splay Tree","Mixed Knapsack","Minimum Enclosing Circle","Perfect Matching","K Shortest Path"]}