366. 4Sum II
You are given four integer arrays nums1, nums2, nums3, and nums4, all of the same length n. Count how many index tuples (i, j, k, l) — one index into each array — make the four chosen values cancel out:
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Tuples are counted by index, so equal values sitting at different positions each contribute their own tuples.
Your function receives the four arrays and returns the number of such tuples.
Example 1:
Input: nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
Output: 2
Explanation: Two tuples work: (0, 0, 0, 1) → 1 + (-2) + (-1) + 2 = 0, and (1, 1, 0, 0) → 2 + (-1) + (-1) + 0 = 0.
Example 2:
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1
Explanation: The only tuple is (0, 0, 0, 0), and 0 + 0 + 0 + 0 = 0.
Constraints:
- 1 ≤ n ≤ 200
- -2²⁸ ≤ nums1[i], nums2[i], nums3[i], nums4[i] ≤ 2²⁸
Hints:
Four nested loops is O(n^4). Notice the equation splits: nums1[i] + nums2[j] must equal -(nums3[k] + nums4[l]) — two independent halves.
Precompute every nums1[i] + nums2[j] into a hash map of sum → occurrence count. Then for each (k, l) pair, add how many left-half pairs sum to the exact negation.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 2], nums2 = [-2, -1], nums3 = [-1, 2], nums4 = [0, 2]
Expected output: 2