LeetCode link:[1. Two Sum](https://leetcode.com/problems/two-sum), difficulty:**Easy**

Given an array of integers`nums` and an integer`target`, return_indices of the two numbers such that they add up to`target`_.

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

**Output**:`[1,2]`

-**Only one valid answer exists.**

1. In`Map`,`key` is`num`, and`value` is array`index`.

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

numToIndex.set(nums[i], i)

}

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

numToIndex.set(nums[i], i)

}

```

2. Traverse the array,if`target - num` isin`Map`,returnit.Otherwise, add`num` to`Map`.

let numToIndex=newMap()

for (let i=0; i<nums.length; i++) {

if (numToIndex.has(target- nums[i])) {// 1

return [numToIndex.get(target- nums[i]), i]// 2

}

numToIndex.set(nums[i], i)

}

### Complexity

* Time:`O(n)`.

<details>

<summary>Hint 1</summary>

So, we essentially need to find three numbersx, y, andz such that they add up to the given value. If we fix one of the numbers sayx, we are left with the two-sum problem at hand!

So, we essentially need to find three numbers`x`,`y`, and`z` such that they add up to the given value. If we fix one of the numbers say`x`, we are left with the two-sum problem at hand!

</details>

<details>

<summary>Hint 2</summary>

For the two-sum problem, if we fix one of the numbers, sayx, we have to scan the entire array to find the next numbery, which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

For the two-sum problem, if we fix one of the numbers, say`x`, we have to scan the entire array to find the next number`y`, which is`value - x` where value is the input parameter. Can we change our array somehow so that this search becomes faster?

</details>

<details>

</details>

1. The`sum` of three numbers equals`0`, which is equivalent to the`sum` of_two numbers_ equaling the_**negative** thirdnumber_.

1. The`sum` of three numbers equals`0`, which is equivalent to the`sum` of*two numbers* equaling the***negative** thirdnumber*.

2. There are two options:

1. First`determine two numbers` and`find the third number`

2. First`determine one number` and`find the other two numbers`

5. For`option 1`, only the`Python` sample code is given. This article focuses on`option 2`.

1. Sort`nums`.

2. Iterate over`nums`.

3. pseudocode:

for (i=0; i<nums.length; i++) {

left= i+1

right=nums.length-1

while (left< right) {

if (condition1) {

left+=1

}else (condition2) {

right-=1

}

}

}

for (i=0; i<nums.length; i++) {

left= i+1

right=nums.length-1

while (left< right) {

if (condition1) {

left+=1

}else (condition2) {

right-=1

}

}

}

```

## Complexity

* Time:`O(N * N)`.

* Space:`O(N)`.

## Python

### Solution1: UseMap (complex and slow)

LeetCode link:[18. 4Sum](https://leetcode.com/problems/4sum), difficulty:**Medium**

Given an array`nums` of`n` integers, return_an array of all the**unique**quadruplets_`[nums[a], nums[b], nums[c], nums[d]]` such that:

Given an array`nums` of`n` integers, return*an array of all the**unique**quadruplets*`[nums[a], nums[b], nums[c], nums[d]]` such that:

*`a`,`b`,`c`, and`d` are**distinct**.

* You may return the answer in**any order**.

-`a`,`b`,`c`, and`d` are**distinct**.

- You may return the answer in**any order**.

**Input**:`nums = [1,0,-1,0,-2,2], target = 0`

1. The idea of this question is the same as[15. 3Sum](15-3sum.md), please click the link to view.

4. You may have already seen that no matter it is`two numbers`,`three numbers` or`four numbers`, the`Two Pointers Technique` can be used.

* Time:`O(N**3)`.

* Time:`O(N^3)`.

* Space:`O(N)`.

1. First find out`node_count`.

node_count=0

node= head

while node

node_count+=1

node= node.next

2. When`index == node_count - N`, delete the node by`node.next = node.next.next`.

index=0

node= head

while node

if index== node_count- n

node.next= node.next.next

index+=1

node= node.next

3. Since the deleted node may be`head`, a virtual node`dummy_node` is used to facilitate unified processing.

dummy_head=ListNode.new# 1

dummy_head.next= head# 2

node= dummy_head# 3

return dummy_head.next

* Time:`O(N)`.