Sitemap
Open in app

Sign in

Medium Logo
Write
Search

Sign in

Neetcode 150 — Two Pointers

5 min readOct 7, 2026

--

最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。

1. Valid Palindrome

// 1. Two pointer
// 判斷 Palindrome 可以用兩個 pointer，從頭和從尾巴，
// 如果遇到不是 alphanumeric，pointer 再移動一格，比較是否一樣。
//
// ex. "Was it a car or a cat I saw?" -> 一開始是 'W'和 '?'，但'？'不是 
// alphanumeric，再移動一格，變成比較 W 和 w，因為不用在意大小寫，因此一樣；
// 接著再比較 'a' 和 'a'；直到 pointer 指到同一個點。
//
// 假設 String s 長度為 n
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// "Was it a car or a cat I saw?" -> true (true)
// "" -> true (empty)
// "?" -> true (一個特殊字元)
// "!?" -> true (全部特殊字元)
// "cartac" -> false (false)
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) != (Character.toLowerCase(s.charAt(right)))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

2. Two Integer Sum II

// 1. Brute force
// 可以 for loop 數字，裡面再放一個 for loop 從接下來的數字找
// ex. numbers = [1,2,3,4], target = 6
// [1], for loop [2-4] 都沒有
// [2], for loop [3-4] 在4時相加等於 target
// 假設 numbers 有 n 個數字
// Time complexity: O(n + n-1 + ... 1) = O(n^2)
// Space complexity: O(1)

// 2. Two pointer
// 從左和右相加比較，如果數字>target，左邊數字向右移；如果數字<target，右邊數字向左移
// ex. numbers = [1,2,3,4], target = 6
// 1+4=5 < 6 -> 2+4=6 得到答案
//
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// numbers = [1,2,3,4], target = 6 -> [1, 3]
// numbers = [], target = 1 -> []
// numbers = [1], target = 1 -> [1]
// numbers = [1,2,3,4], target = 8 -> []
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right]; // 要確認相加不會超過結果
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{};
    }
}

Get AShiou’s stories in your inbox

Join Medium for free to get updates from this writer.

3. 3Sum

// 1. Brute force
// for loop 數字，裡面再一個 for loop 接下來的數字，再裡面再一個 for loop 接下來的數字
// ex. [-1,0,1,2,-1,-4]
// [-1],[0], for loop [1, 2, -1, -4]在 -1+0+1=0時找到答案
// 假設 numbers有n個數字
// Time complexity: O(n^3)
// Space complexity: O(1)

// 2. Hashmap
// 先把數字放進hashmap，key為數字，value為count
// 進行 sort，讓 duplicate handling 變容易
// 然後 for loop 數字，要比對數字跟上一個開頭的數字是否相同，相同就要skip，避免答案重複。
// 選一個數字後，裡面再一個 for loop 接下來的數字，看hashmap有沒有能一起相加為0的
// ex. [-1,0,1,2,-1,-4], sort 後為 [-4,-1,-1,0,1,2]
// [-4],for loop [-1,-1,0,1,2] 然後看hashmap有沒有相加為0的
// [-1],for loop [-1,0,1,2] -> 得到 [-1,-1,2],[-1,0,1]
// [-1] 因為和上一個開頭的數字相同，skip
// [0],for loop [1,2]
// [1], for loop [2]
// Time complexity: O(n^2)
// Space complexity: O(n)

// 3. Sort + two pointers
// 先 sort，然後for loop 選定一個數字，接著 two pointers 剩下的數字，看相加能否為0
// ex. [-1,0,1,2,-1,-4], sort 後為 [-4,-1,-1,0,1,2]
// [-4], two pointers 做 [-1,-1,0,1,2]
// [-1], two pointers 做 [-1,0,1,2]
// [-1]因為和上一個開頭的數字相同，skip
// ...
// Time complexity: O(n^2)
// Space complexity: O(1)
//
// Dry run
// [-4,-1,-1,0,1,2] -> [-1,-1,2], [-1,0,1]
// [] -> []
// [-1] -> []
// [-1,0,0,1,1] -> [-1,0,1] two pinters 要注意是否跟之前的一樣
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(List.of(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

4. Container With Most Water

// 1. Brute force
// for loop 數字，再裡面 for loop 接下來的數字，找出最大值
// 假設 height 有 n 個值
// Time complexity: O(n^2)
// SPace complexity: O(1)

// 2. Two pointers
// 從最左和最右開始，算出值後；接著移動較小的值，再算出值
// ex. height = [1,7,2,5,4,7,3,6]
// left=1,right=6,width=7->1*7=7,移動left,因為移right算出的值只會隨著width越來越小
// left=7,right=6,width=6->6*6=36,移動right
// ...
//
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// [1,7,2,5,4,7,3,6] -> 42
// [] -> 0
// [1] -> 0
// [1,1] -> 1
class Solution {
    public int maxArea(int[] heights) {
        int max = 0;
        int left = 0;
        int right = heights.length - 1;
        while (left < right) {
            boolean leftSmaller = heights[left] <= heights[right];
            int width = right - left;
            if (leftSmaller) {
                max = Math.max(heights[left] * width, max);
                left++;
            } else {
                max = Math.max(heights[right] * width, max);
                right--;
            }
        }
        return max;
    }
}

5. Trapping Rain Water

// 1. Brute force
// for loop值，在當時的值看左邊最大值，右邊最大值，算當格的容量
// ex. height = [0,2,0,3,1,0,1,3,2,1]
// [0] -> 左邊沒值, skip
// [2] -> 左邊變小, skip
// [0] -> 左邊最大2, 右邊最大3 -> 2
// [3] -> 左邊變小, skip
// [1] -> 左邊最大3,右邊最大3 -> 3-1=2
// [0] -> 3
// [1] -> 3-1=2
// [3] -> 左邊一樣，右邊變小，skip
// [2] -> 右變變小，skip
// [1] -> 右邊沒值，skip
// 2+2+3+2=9
//
// 假設height 有 n 個
// Time complexity: O(n^2)
// Space complexity: O(1)

// 2. Prefix & Suffix Array
// 建一個 left array，記錄當前左邊的最大值；再建一個 right array，記錄當前右邊的最大值
// 在跑 Height 時，就可以根據左右值來判斷能不能裝雨水
// ex. height = [0,2,0,3,1,0,1,3,2,1]
//.      left = [0,0,2,2,3,3,3,3,3,3]
//      right = [3,3,3,3,3,3,3,2,1,0]
// [0] -> left<=0
// [2] -> left<=2
// [0] -> Math.min(2,3) -> 2-0=2
// [3] -> left<=3
// [1] -> Math.min(3,3) -> 3-1=2
// [0] -> Math.min(3,3) -> 3-0=3
// [1] -> Math.min(3,3) -> 3-1=2
// [3] -> right<=3
// [2] -> right<=2
// [1] -> right<=1
// 2+2+3+2=9
//
// Time complexity: O(n)
// Space complexity: O(n)
class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int[] left = new int[len];
        int[] right = new int[len];

        for (int i = 0; i < len; i++) {
            if (i == 0) {
                left[i] = 0;
                continue;
            }
            left[i] = Math.max(left[i-1], height[i-1]);
        }

        for (int i = len - 1; i >= 0; i--) {
            if (i == len - 1) {
                right[i] = 0;
                continue;
            }
            right[i] = Math.max(right[i+1], height[i+1]);
        }

        int sum = 0;
        for (int i = 0; i < len; i++) {
            if (left[i] <= height[i] || right[i] <= height[i]) {
                continue;
            }
            sum = sum + Math.min(left[i], right[i]) - height[i];
        }
        return sum;
    }
}

// 3. Two pointers
// 可以不用 array 記左右的最大值，而是一開始把leftMax從最前面開始，rightMax從最後端開始，
// 選Math.min(leftMax,rightMax)當作結果來算，接著移動最小的pointer
//
// Time complexity: O(n)
// Space complexity: O(1)
// 
// Dry run
// [0,2,0,3,1,0,1,3,2,1]
// [] -> 0
// [1] -> 0
// [1,2] -> 0
class Solution {
    public int trap(int[] height) {
        if (height.length < 1) {
            return 0;
        }
        int sum = 0;
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        while (left < right) {
            if (leftMax <= rightMax) {
                left++;
                if (height[left] < leftMax) {
                    sum = sum + leftMax - height[left];
                } else {
                    leftMax = Math.max(height[left], leftMax);
                }
            } else {
                right--;
                if (height[right] < rightMax) {
                    sum = sum + rightMax - height[right];
                } else {
                    rightMax = Math.max(height[right], rightMax);
                }
            }
        }
        return sum;
    }
}
Two Pointers
Neetcode 150
Software Interview
Leetcode

--

--

AShiou
AShiou

Written by AShiou

7 followers
54 following

Help

Status

About

Careers

Press

Blog

Store

Privacy

Rules

Terms

Text to speech