方法一:暴力解法 888ms
class Solution {
public int triangleNumber(int[] nums) {
int ans = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
for (int k = nums.length - 1; k - i > 1 ; k--) {
for (int j = i + 1; j < k; j++) {
if (nums[i] + nums[j] > nums[k]){
ans += k - j;
break;
}
}
}
}
return ans;
}
}
方法二:排序 + 二分查找 288ms
class Solution {
public int triangleNumber(int[] nums) {
int ans = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
int left = j + 1;
int right = nums.length - 1;
int k = j;
//找到最大的k满足条件 i + j > k
while (left <= right){
int mid = (left + right) / 2;
if (nums[i] + nums[j] > nums[mid]){
k = mid;
left = mid + 1;
}else {
right = mid - 1;
}
}
ans += k - j;
}
}
return ans;
}
}
方法三:排序 + 双指针
在方法二的基础上改进
class Solution {
public int triangleNumber(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int ans = 0;
for (int i = 0; i < n; ++i) {
int k = i;
for (int j = i + 1; j < n; ++j) {
while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
++k;
}
//k - j可能小于0,ans要加一个正数
ans += Math.max(k - j, 0);
}
}
return ans;
}
}
2.剑指 Offer 53 – II. 0~n-1中缺失的数字 ⭐⭐⭐⭐⭐
二分法
排序数组中的搜索问题,首先想到 二分法 解决
class Solution {
public int missingNumber(int[] nums) {
int i = 0, j = nums.length - 1;
while(i <= j) {
int m = (i + j) / 2;
if(nums[m] == m) i = m + 1;
else j = m - 1;
}
return i;
}
}
3.剑指 Offer 53 – I. 在排序数组中查找数字 I
普通的二分查找
查找等于目标值的所有位置
class Solution {
public int search(int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
int ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (target > nums[mid]){
l = mid + 1;
}else if (target < nums[mid]){
r = mid - 1;
}else {
ans++;
for (int i = mid - 1; i >= 0; i--) {
if (nums[i] == target)ans++;
else break;
}
for (int i = mid + 1; i < nums.length; i++) {
if (nums[i] == target)ans++;
else break;
}
break;
}
}
return ans;
}
}
4.剑指 Offer 51. 数组中的逆序对
二分 + 分治思想
class Solution {
int ans = 0;
public int reversePairs(int[] nums) {
split(nums,0,nums.length - 1);
return ans;
}
//分
public void split(int[] nums,int l,int r){
if (l >= r)return;
int mid = (l + r) / 2;
split(nums,l,mid);
split(nums,mid + 1,r);
merge(nums,l,mid,r);
}
//合
private void merge(int[] nums, int l, int mid, int r) {
int left = l;
int right = mid + 1;
List list = new ArrayList<>();
while (left <= mid && right <= r){
if (nums[right] < nums[left]){
list.add(nums[right]);
right++;
}else {
ans += right - mid - 1;
list.add(nums[left]);
left++;
}
}
while (left <= mid){
ans += right - mid - 1;
list.add(nums[left]);
left++;
}
while (right <= r){
list.add(nums[right]);
right++;
}
for (int i = 0; i < list.size(); i++) {
nums[l++] = list.get(i);
}
}
}
5.寻找峰值( LeetCode 162 )
方法一:寻找最大值
由于题目保证了 nums[i] ≠ [i+1] ,那…么数组 nums中最大值两侧的元素一定严格小于最大值本身。因此,最大值所在的位置就是一个可行的峰值位置。
class Solution {
public int findPeakElement(int[] nums) {
int idx = 0;
for (int i = 1; i < nums.length; ++i) {
if (nums[i] > nums[idx]) {
idx = i;
}
}
return idx;
}
}
方法二:迭代爬坡
我们总是往高处走总能找到山峰
class Solution {
public int findPeakElement(int[] nums) {
int idx = 0;
while (!(compare(nums,idx - 1,idx) < 0 && compare(nums,idx,idx + 1) > 0)){
//如果右侧高则向右侧移动
if(compare(nums,idx,idx + 1) < 0){
idx++;
}else {//否则向左侧移动
idx--;
}
}
return idx;
}
//比较nums中两个位置的大小
public int compare(int[] nums,int l,int r){
if (l == -1)return -1;
if (r == nums.length)return 1;
return nums[l] - nums[r];
}
}
方法三:方法二的二分实现
在上述算法中,如果我们固定选取 i 为 [l,r] 的中点,那么每次可行的下标范围会减少一半,成为一个类似二分查找的方法,时间复杂度为O(logn)。
class Solution {
public int findPeakElement(int[] nums) {
int idx = 0;
int left = 0;
int right = nums.length - 1;
while (left <= right){
int mid = (left + right) / 2;
if (compare(nums,mid - 1,mid) < 0 && compare(nums,mid,mid + 1) > 0){
idx = mid;
break;
}
if(compare(nums,mid,mid + 1) < 0){
left = mid + 1;
}else {
right = mid - 1;
}
}
return idx;
}
public int compare(int[] nums,int l,int r){
if (l == -1)return -1;
if (r == nums.length)return 1;
return nums[l] - nums[r];
}
}



