題目：15. 3Sum

連結：https://leetcode.com/problems/3sum/description/

• 等級：Medium

解題思路

1. 對輸入陣列進行排序
2. 初始化一個集合來存儲唯一的三元組，並初始化一個輸出向量來存儲最終結果
3. 使用變量i從索引0開始迭代遍歷陣列
4. 初始化兩個指針j和k，j從i+1開始，k從陣列的末尾開始
5. 在while循環中，檢查nums[i]、nums[j]和nums[k]的和是否等於0。如果是，將三元組插入集合中，並將j增加1，k減少1以移動指針
6. 數值相同略過不計算
7. 如果和小於0，增加j。如果和大於0，減少k。
8. while循環結束後，遍歷集合，將每個三元組添加到輸出向量中
9. 返回輸出向量

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int target = 0;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0;i < nums.length;i++)
        {
            int j = i + 1;
            int k = nums.length - 1;
            if(i!=0 && nums[i]==nums[i-1]) continue;
            while (j < k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target)
                {
                    List<Integer> temp=Arrays.asList(nums[i],nums[j],nums[k]);
                    result.add(temp);
                    j++;
                    k--;
                    while(j<k && nums[j]==nums[j-1]) j++;
                    while(j<k && nums[k]==nums[k+1]) k--;
                }
                else if (sum < target)
                {
                    j++;
                }
                else
                {
                    k--;
                }
            }
        }
        return result;
    }
}

• Time complexity: O(n^2 logn)
• Space complexity: O(n)

題目：6. Zigzag Conversion

連結：https://leetcode.com/problems/3sum/description/

• 等級：Medium

• 等級：Medium

解題思路

可以使用兩個巢狀循環，一個用於計算行，一個用於計算每行中的字元。我們也可以使用一個變數來追蹤每個迴圈的長度，在本例中為 2 * numRows - 2。在每次回圈計算中，我們可以將字元新增到模式中對應的行中，如果存在的話，也可以在下一個循環中加入對應的字元。

• 對於每一行，我們需要跳過第一行和最後一行的字符，因為在下一個循環中沒有對應的字符。
• 對於中間的行，我們需要在下一個循環中加入對應的字元。
• 我們可以使用字串變數來儲存轉換後的字串，並在最後返回它。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1)
            return s;
        StringBuilder result = new StringBuilder();
        int len = s.length();
        int cycle = 2 * numRows - 2;
        for (int i = 0;i < numRows; i++) {
            for (int j = 0; j+i < len; j += cycle) {
                result.append(s.charAt(j + i));
								//第一個最後一個只出現一次
								//中間每個循環會出現兩次
								//第二次由循環尾加到前面
                if (i != 0 && i != numRows - 1 && j + cycle - i < len) {
                    result.append(s.charAt(j + cycle - i));
                }
            }
        }
        return result.toString();
    }
}

• Time complexity: O(n)
• Space complexity: O(n)