15. 三數(shù)之和

題意：給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有和為 0 且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。

解題思路

解法1：
1.分析題意，三層for循環(huán)部分，需要優(yōu)化，暴力解法超時(shí)
2.已排序+雙指針+重合判斷，解決超時(shí)問題
3.兩個(gè)指針重合，代表隨著b的后推，不會(huì)再有滿足條件的值，因?yàn)榇藭r(shí)nums是從小到大排序的
4.需要解決重復(fù)元素的問題，轉(zhuǎn)化為如何解決重復(fù)元素問題

解題遇到的問題

無(wú)

后續(xù)需要總結(jié)學(xué)習(xí)的知識(shí)點(diǎn)

無(wú)

##解法1
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        // 結(jié)果鏈表
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length <= 2) {
            return result;
        }
        Arrays.sort(nums);
        // a+b+c=0
        HashSet<String> set = new HashSet<String>();
        // 三層for循環(huán)部分，需要優(yōu)化，暴力解法超時(shí)
        // 已排序+雙指針+重合判斷，解決超時(shí)問題
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int target = -nums[i];
                int k = nums.length - 1;
                while (nums[j] + nums[k] > target && j < k) {
                    k--;
                }

                // 兩個(gè)指針重合，代表隨著b的后推，不會(huì)再有滿足條件的值，因?yàn)榇藭r(shí)nums是從小到大排序的
                if (j == k) {
                    break;
                }

                if (nums[k] + nums[j] + nums[i] == 0) {
                    StringBuilder builder = new StringBuilder();
                    // 需要解決重復(fù)元素的問題，轉(zhuǎn)化為如何解決重復(fù)元素問題
                    int[] temp = new int[]{nums[i], nums[j], nums[k]};
                    Arrays.sort(temp);
                    builder.append(temp[0]).append(temp[1]).append(temp[2]);
                    if (set.add(builder.toString())) {
                        List<Integer> t = new ArrayList<Integer>();
                        t.add(nums[i]);
                        t.add(nums[j]);
                        t.add(nums[k]);
                        result.add(t);
                    }
                }
            }
        }
        return result;
    }
}