欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

有效三角形的个数

题目链接

解法

解法1:暴力枚举--->O(n^3)

解法2:利用单调性,使用双指针来解决---->O(n^2)

优化:对整个数组进行排序先固定最大数在最大数的左区间内,使用双指针算法,快速统计出符合要求的个数

统计分为两种情况:

能构成三角形的 a+b>c 不能构成三角形的 a+b<=c 

画图举例

代码

<code>class Solution {

public int triangleNumber(int[] nums) {

Arrays.sort(nums);

int n=0,i=nums.length-1;

while(i>=2){

int left=0,right=i-1;

while(left<right){

if(nums[left]+nums[right]>nums[i]){

n+=(right-left);

right--;

}else{

left++;

}

}

i--;

}

return n;

}

}

class Solution {

public int triangleNumber(int[] nums) {

Arrays.sort(nums);

int ret=0,n=nums.length;

for(int i =n-1;i>=2;i--){

int left=0,right=i-1;

while(left<right){

if(nums[left]+nums[right]>nums[i]){

ret+=(right-left);

right--;

}else{

left++;

}

}

}

return ret;

}

}

查找总价格为目标值的两个商品

题目链接

解法

解法一:暴力枚举,时间复杂度:O(n^2)--->超时

解法二:利用单调性,使用双指针算法解决,时间复杂度:O(n)

用sum表示两数相加的值,t表示目标值,无非就三种情况:

sum<t  ---->left++sum>t  --->right--sum=t  ---->返回结果

注意:本题一定是有返回结果的,但为了照顾编译器,最后可以随意返回一个数组

画图举例

代码

<code>class Solution {

public int[] twoSum(int[] price, int target) {

int sum=0,left=0,right=price.length-1;

while(left<right){

sum=price[left]+price[right];

if(sum<target){

left++;

}else if(sum>target){

right--;

}else{

return new int[]{price[left],price[right]};

}

}

//照顾编译器

return new int[]{0};

}

}

三数之和

题目链接

解法

解法一:排序+暴力枚举+利用set去重, 时间复杂度:O(n^3)

解法二:排序+双指针

排序固定一个数a在该数后面的区间内,利用"双指针算法"快速找到两个数的和等于 -a即可

处理细节问题:

去重

找到一种结果后,left和right指针要跳过重复的元素,当使用完一次双指针算法之后,i也要跳过重复元素(细节1和2都要避免越界)不漏

找到一种结果之后,不要停,缩小区间,继续寻找

画图举例

代码

<code>class Solution {

public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> ret=new ArrayList<>();

int n=nums.length;

for(int i = 0;i < n;){

if(nums[i] > 0) break;

int left=i+1,right =n-1,target=-nums[i];

while(left < right){

int sum=nums[left]+nums[right];

if(sum > target) right--;

else if(sum < target) left++;

else{

ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));

left++;right--;//缩小区间,继续寻找

//left,right去重

while(left < right && nums[left] == nums[left-1]) left++;

while(left < right && nums[right] == nums[right+1]) right--;

}

}

i++;

//i去重

while(i < n && nums[i] ==nums[i-1]) i++;

}

return ret;

}

}

四数之和

题目链接

解法

解法1:排序 + 暴力枚举 + 利用set去重

解法2: 排序 + 双指针(主要利用"三数之和"(上一题)的思路)

依次固定一个数a;在a后面的区间内,利用"三数之和" 找到三个数,是这三个数等于target-a即可

依次固定一个数b在b的后面的区间内,利用双指针找到两个数,是这两个数的和等于target-a-b即可

处理细节:

不重不漏

画图举例

代码

<code>class Solution {

public List<List<Integer>> fourSum(int[] nums, int target) {

Arrays.sort(nums);

List<List<Integer>> ret = new ArrayList<>();

int n = nums.length;

for(int i=0;i<n;){//固定数a

for(int j=i+1;j<n;){//固定数b

int left=j+1,right=n-1;

long aim=(long)target-nums[i]-nums[j];//可能有溢出的风险,所以用long

while(left<right){

int sum = nums[left] + nums[right];

if(sum > aim) right--;

else if(sum < aim) left++;

else{

ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));

left++; right--;

//left 和 right 去重

while(left < right && nums[left] == nums[left-1]) left++;

while(left < right && nums[right] == nums[right+1]) right--;

}

}

j++;

//j去重

while(j<n && nums[j] == nums[j-1]) j++;

}

i++;

//i去重

while(i<n && nums[i] == nums[i-1]) i++;

}

return ret;

}

}