3sum 4sum

[remlostime]

Checklist

• I've looked at the contribution guidelines.
• This pull request is complete and ready for review.

Description

Follow up 2Sum problem. How to solve 3Sum and 4Sum problem? What’s their relationships? Could we get some generic idea to solve this kind of problems? I give the explanation here.

[kelvinlauKL]

@remlostime I initially just wanted to leave a few comments, but I ended up doing a full blown edit :]

I wanted to give you some feedback based on what I saw:

• avoid barrages of rhetorical questions. Here's an offender:

The key idea here is we split the array into 2 parts, if we have a pointer i, let’s assume we got i position already. What’ next? Actually, next is just a 2Sum problem right? We can just apply 2 pointers method in 2Sum. But what’s 2Sum’s target sum? Is it target2Sum = target3Sum - nums[i] ? That’s awesome!

I personally avoid asking the reader questions in my writing, but it's fine once in a while. 4 times in a short paragraph is a bit too much, and berates readers who weren't too savvy in connecting the dots, like myself :]

• "avoiding duplicates"

I'm a little confused by your explanation in avoiding duplicates. You wrote:

How we avoid duplicate triplets? Since the array has been sorted, we just need to check if a[i] == a[i-1]. Why? Because if a[i] == a[i-1], it means that a[i-1] already covers all a[i] solutions, we should not do it, otherwise it will have duplicate answers.

Correct me if I'm wrong, but it implied to me that I should avoid using a[i] if it has the same value as a[i - 1]. If that's true, your example in the beginning doesn't really make sense:

[-1, 0, 1, 2, -1, -4] // unsorted
[-4, -1, -1, 0, 1, 2] // sorted

[[-1, 0, 1], [-1, -1, 2]] // solution set

Since the -1 values are together, [-1, -1, 2] wouldn't be a solution would it?

---

Anyhow, thanks for the PR. So far, I've done editing for the 3Sum via aeffa0a. Once you've addressed my concern on the "avoiding duplicates" part, could revisit your 4Sum writeup and rewrite it based on the changes I've made to 3Sum?

Thanks!

[kelvinlauKL]

@remlostime There's a cool editor called the Hemmingway editor that really helped my writing in the past. Consider checking it out when you do article writing: http://hemingwayapp.com

[remlostime]

@kelvinlauKL Thanks a lot for the awesome editing and writing app!
Here is deeper explanation about avoid duplicates.

[-1, 0, 1, 2, -1, -4] // unsorted

1)
[-4, -1, -1, 0, 1, 2]
      i   l        r

2)
[-4, -1, -1, 0, 1, 2]
          i  l     r

3)
[-4, -1, -1, 0, 1, 2]
      i      l     r

We have three pointers i, l, r. We loop i from 0..<n, each loop we have another inner loop, l..r which start from i+1..<n.
In 1), we will check if a[i] == a[i-1]? It's not in this case, then we decrease the problem to 2sum, the array ranging l..r
In 2), Since a[i] == a[i-1], it means a[i-1] covers a[i] case. Because case 3) contains case 2) solutions.

[kelvinlauKL]

@remlostime I tried to simplify the writing a bit. I'm still a little confused. Here's an example:

[-4, -1, -1, -1, -1, 0, 1, 2]
          i   

• a[i] == -1
• a[i - 1] == -1

Would we have multiple [-1, -1, 2] subsets? or only 1?

[remlostime]

@kelvinlauKL In that cases, we will have multiple

[-1, -1, 2]

For example,

[-1, -1, -1, 2]

The answer should be two [-1, -1, 2]

[kelvinlauKL]

Ok, thanks for the clarification. I'll continue with this review (could you also squash those merge conflicts please).

[remlostime]

Update the PR and fix the conflict. @kelvinlauKL

[kelvinlauKL]

@remlostime I think I found a bug:

threeSum([-1, -1, -1, -1, 2, 1, -4, 0], targetSum: 0)

// result [[-1, -1, 2], [-1, 0, 1]]

threeSum([-1, -1, -1, -1, -1, -1, 2], targetSum: 0)

// result [[-1, -1, 2]]

While you're at it, could you rename the variables of your code to l, m and r respectively? It's a bit more relatable than i, j, and k, and that'll make it match the README explanation better.

[remlostime]

@kelvinlauKL I looked in to code again. And find this

if l != 0 && a[l] == a[l-1] {
  l += 1
  flag = true
}

if (r != a.count - 1) && a[r] == a[r+1] {
  r -= 1
  flag = true
}

So, I think that's why you see the unique result. Since this PR is pretty long time ago, I just recall that should make sense to just keep unique answers. Sorry for the confusing.

PR has been updated.

[kelvinlauKL]

@remlostime Works for me!

[kelvinlauKL]

@remlostime Merging this in :) Thanks!

[remlostime]

Thanks for the awesome edit!!! @kelvinlauKL
💯💯💯💯💯💯💯💯💯💯💯