C语言Brute Force实现3Sum——如何检测重复三元组？

Hey there! I totally get where you're coming from—brute-force for 3Sum works for finding triplets that add up to zero, but filtering out duplicates can feel tricky at first. Let's walk through two straightforward approaches to fix this:

Approach 1: Sort First, Skip Duplicate Elements #

This is my go-to for brute-force because it avoids generating duplicates in the first place, which is more efficient than cleaning them up later. Here's how it works:

• Sort the input array: When you sort nums, identical elements will be grouped together. This makes it easy to skip over values we've already processed.
• Skip duplicates in each loop:
  • For the first loop (index i), if the current value is the same as the previous one (and i isn't the first element), skip it—we already checked all triplets starting with that value.
  • Do the same for the second loop (index j): if j isn't right after i and the current value matches the previous, skip it.
  • The third loop can proceed as usual, since we've already eliminated duplicate starting pairs.

Here's a Python code example to illustrate:

def threeSum(nums):
    nums.sort()
    n = len(nums)
    result = []
    
    for i in range(n):
        # Skip duplicate i values
        if i > 0 and nums[i] == nums[i-1]:
            continue
        
        for j in range(i + 1, n):
            # Skip duplicate j values (only if j is not immediately after i)
            if j > i + 1 and nums[j] == nums[j-1]:
                continue
            
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])
    
    return result

Approach 2: Use a Set to Track Seen Triplets #

If you don't want to sort the array first, you can use a set to keep track of triplets you've already added to the result. The key here is to normalize each triplet so that different orderings of the same values are treated as duplicates:

• Generate the triplet: When you find a triplet that sums to zero, sort it (so [-1, 0, 1] and [0, -1, 1] become the same sorted tuple).
• Check the set: If the sorted tuple isn't in the set, add it to both the set and the result list.

Here's what that looks like in code:

def threeSum(nums):
    n = len(nums)
    seen_triplets = set()
    result = []
    
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    # Sort the triplet to normalize it
                    sorted_triplet = tuple(sorted([nums[i], nums[j], nums[k]]))
                    if sorted_triplet not in seen_triplets:
                        seen_triplets.add(sorted_triplet)
                        result.append(list(sorted_triplet))
    
    return result

A quick note: This approach is simpler to wrap your head around, but it's less efficient than the sorted method because you're generating duplicate triplets first and then filtering them out. For large arrays, the first approach will perform better.

Also, just a reminder—while brute-force works, the optimal 3Sum solution uses a two-pointer technique (after sorting) which cuts the time complexity down to O(n²) instead of O(n³). But since you're focused on brute-force right now, these two methods should solve your duplicate problem!

内容的提问来源于stack exchange，提问作者Sunny