4Sum
Find every group of four money moves that lands exactly on your goal. nums holds your moves for a stretch of days: deposits are positive and spending is negative. Return every different group of four moves whose total is exactly target. The four moves must come from four different places in the list. A group is listed once, however many copies of its values nums holds. Groups can come back in whatever order you like, and so can the four values inside a group. Limits: 1 <= nums.length <= 400, -1000000000 <= nums[i] <= 1000000000, -1000000000 <= target <= 1000000000. Think about: four values near a billion add up to well past a 32-bit int. Example: nums = [3,-1,0,2,-3,1,0,2], target = 2 [-3,0,2,3] adds up to 2 [-3,1,2,2] adds up to 2 [-1,0,0,3] adds up to 2 (two 0s in the list, still one group) [-1,0,1,2] adds up to 2 Those four groups are the whole answer.
You're hunting for every group of four numbers that adds up to a target, with no group listed twice. It's the natural next step after 3Sum, and interviewers use it to see whether you can stretch a pattern you already know. The classic traps are duplicate groups and sums that quietly overflow a 32-bit int. Expect up to 400 numbers, each up to a billion in size, and a target in the same range.
Examples
You write
four_sum(nums: List[int], target: int)
Example 1
- Input
- nums = [3,-1,0,2,-3,1,0,2], target = 2
- returns
- [[-3,0,2,3],[-3,1,2,2],[-1,0,0,3],[-1,0,1,2]]
Example 2
- Input
- nums = [1,1,1,1,2,2,2,2,0,0,0], target = 4
- returns
- [[0,0,2,2],[0,1,1,2],[1,1,1,1]]
Save this for your laptop
The editor and Run need a bigger screen. The link opens 4Sum ready to code. It is free, and the editor needs no account.
The pattern behind it
Two Pointers
I reach for it when
- The array is sorted, or you can sort it.
- You need a pair, a triple or a palindrome.
Say this before you type. Say what each pointer means and what a move to the left or right rules out.
All 26 Two Pointers problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.