数组简介

1. LeetCode 1991 找到数组的中间位置

方法1：前缀和

class Solution {
    public int findMiddleIndex(int[] nums) {
        int tol = 0, s = 0;
        for(int num : nums) 
            tol += num;
        for(int i = 0; i < nums.length; i++) {
            if(s == tol - s - nums[i])
                return i;
            s += nums[i];
        }
        return -1;
    }
}

2. LeetCode 35 搜索插入位置

方法1：二分查找

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length;
        while(left < right) {
            int mid = (left + right) >> 1;
            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        return left;
    }
}

3. LeetCode 56 合并区间

方法1：贪心

• 排序 (a, b) -> a[0] - b[0]
• 列表转数组 toArray(new int[M][N])

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int []> ans = new ArrayList<int []>();
        for(int[] info : intervals) {
            int n = ans.size(), left = info[0], right = info[1];
            // 数组为空 或 区间不能合并
            if(n == 0 || ans.get(n - 1)[1] < left)
                ans.add(info);
            else // 进行合并区间
                ans.get(n - 1)[1] = Math.max(ans.get(n - 1)[1], right);
        }
        return ans.toArray(new int[ans.size()][2]);
    }
}

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        ans = list()
        for (left, right) in intervals:
            # 列表为空 或 区间不能合并
            if not ans or ans[-1][1] < left:
                ans.append([left, right])
            else: # 区间可以合并
                ans[-1][1] = max(ans[-1][1], right)
        return ans

二维数组简介

字符串简介

双指针技巧