Implement the fourSumPairCountSimple method that counts quadruplets that produce the target sum.
The input contains an integer array nums, its length size, and an integer target. Your task is to count how many unique groups of four numbers have a sum equal to target.
Each number can be used only once in a group. Groups with the same values should be counted only once, even if the same values appear at different positions.
For example, for [1,0,-1,0,-2,2] and target 0, there are 3 unique quadruplets.
Example 1
[1,0,-1,0,-2,2]603Example 2
[2,2,2,2]481Example 3
[1,2,3,4]4500Use sorting with two fixed indexes and two moving pointers.
After sorting, fix the first two values using nested loops. For the remaining part of the array, use a left pointer and a right pointer to find pairs that complete the target sum.
If the sum is too small, move the left pointer forward. If the sum is too large, move the right pointer backward. When a valid quadruplet is found, increase the count and skip duplicate values so the same group is not counted again.
Pseudocode:
function fourSumPairCountSimple(nums, size, target):
sort nums in ascending order
count = 0
for i from 0 to size - 4:
if i > 0 and nums[i] == nums[i - 1]:
continue
for j from i + 1 to size - 3:
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = size - 1
while left < right:
sum = nums[i] + nums[j] + nums[left] + nums[right]
if sum == target:
count++
left++
right--
while left < right and nums[left] == nums[left - 1]:
left++
while left < right and nums[right] == nums[right + 1]:
right--
else if sum < target:
left++
else:
right--
return count