三数之和 + 在排序数组中查找元素的第一个和最后一个位置

三数之和(中等)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        if(n == 0) return {};
        vector<vector<int>> res;
        
        for(int i =0; i <n-2 ;++i){
            if(nums[i] > 0) break;
            if(i!=0 && nums[i-1] == nums[i]) {continue;}
            int target = 0- nums[i];
            int j = n-1, k = i+1;
            while(k < j){
                int temp = nums[k] + nums[j];
                if( temp == target){
                    res.push_back({nums[i],nums[k],nums[j]});
                    k++; 
                    j--;
                    while(k< j && nums[k] == nums[k-1]) k++;
                    while(j >k &&nums[j] == nums[j+1]) j--;
                }
                else if(temp < target){k++;}
                else{
                    j--;
                }
            }
        }
        return res;
    }
};

在排序数组中查找元素的第一个和最后一个位置

二分法

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0) return {-1,-1};//
        int l = 0, r = n-1,mid,resl=-1,resr=-1;
        while(l <= r){
            int mid = l+ (r-l)/2;
            if(nums[mid] <= target){if(nums[mid] == target){resr = mid;}l = mid+1;}
            else if(nums[mid] > target){r =mid-1;}
            
        }
        int left = 0, right = n-1;
         while(left <= right){
            int mid = left+ (right-left)/2;
            if(nums[mid] < target){left = mid+1;}
            else if(nums[mid] >= target){if(nums[mid] == target){resl = mid;};right =mid-1;}
            
        }
        if(resl == -1||resr==-1) return {-1,-1};
        return {resl,resr};
    }
};

搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};