当前位置: 首页 > news >正文

深圳app定制开发报价单广州网络优化最早的公司

深圳app定制开发报价单,广州网络优化最早的公司,wordpress 如何分页,营销型网站建设优化问题描述 思路分析 1. 排序数组 目的: 将数组 arr 按升序排序,这样可以方便地使用双指针找到满足条件的三元组,同时避免重复的三元组被重复计算。优势: 数组有序后,处理两个数和 target - arr[i] 的问题可以通过双指针快速找到所有可能的组…

问题描述

在这里插入图片描述


思路分析

1. 排序数组

  • 目的: 将数组 arr 按升序排序,这样可以方便地使用双指针找到满足条件的三元组,同时避免重复的三元组被重复计算。
  • 优势:
    • 数组有序后,处理两个数和 target - arr[i] 的问题可以通过双指针快速找到所有可能的组合。

2. 使用双指针寻找目标对

  • 核心思路:
    • 对于每个固定的元素 a = arr[i] ,寻找剩下的两个元素 b , c 使得 a + b + c = target ,即 b + c = target - a
    • leftright 分别指向当前子数组的起点和终点(i + 1arr.length - 1),通过比较 arr[left] + arr[right]target - arr[i] 的大小调整指针:
      • 如果 arr[left] + arr[right] < target - arr[i] ,说明需要更大的数,移动 left
      • 如果 arr[left] + arr[right] > target - arr[i] ,说明需要更小的数,移动 right
      • 如果两者相等,记录满足条件的对,并继续移动指针。

3. 处理重复元素

在满足条件时,需要仔细处理 arr[left]arr[right] 的重复计数:

  • 情况1: 如果 arr[left] != arr[right]
    • 统计所有重复的 arr[left]arr[right] 的数量,假设重复次数分别为 countLeftcountRight,则可以形成的三元组数为 countLeft × countRight
  • 情况2: 如果 arr[left] == arr[right]
    • 说明所有元素都相等,假设重复次数为 n,则可以形成的三元组数为:

在这里插入图片描述

  • n 表示元素的重复次数。
  • (n−1) 是从剩余元素中选择的方式数。

4. 结果取模

由于结果可能非常大,每次更新结果时都需要对 10⁹ + 7 取模,避免溢出。

算法复杂度

  • 时间复杂度:时间复杂度为 O(n²)
  • 空间复杂度: 只使用了常数级的额外空间,复杂度为 O(1)

参考代码(Java)

import java.util.Arrays;public class Main {public static int solution(int[] arr, int t) {int MOD = 1_000_000_007;Arrays.sort(arr); // 排序int n = arr.length;long count = 0;for (int i = 0; i < n - 2; i++) {int target = t - arr[i];int left = i + 1, right = n - 1;while (left < right) {if (arr[left] + arr[right] == target) {if (arr[left] == arr[right]) { // 如果左指针和右指针值相同int num = right - left + 1;count += (long) num * (num - 1) / 2; // 组合数C(num, 2)count %= MOD;break;} else { // 如果左指针和右指针值不同int leftCount = 1, rightCount = 1;// 统计左指针相同值的个数while (left + 1 < right && arr[left] == arr[left + 1]) {left++;leftCount++;}// 统计右指针相同值的个数while (right - 1 > left && arr[right] == arr[right - 1]) {right--;rightCount++;}// 累加计数count += (long) leftCount * rightCount;count %= MOD;left++;right--;}} else if (arr[left] + arr[right] < target) {left++;} else {right--;}}}return (int) count;}public static void main(String[] args) {System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 4, 5, 5}, 8) == 20);System.out.println(solution(new int[]{2, 2, 2, 2}, 6) == 4);System.out.println(solution(new int[]{1, 2, 3, 4, 5}, 9) == 2);System.out.println(solution(new int[]{1, 1, 1, 1}, 3) == 4);}
}

代码分析

1. 排序和初始化

Arrays.sort(arr); // 排序
int n = arr.length;
long count = 0;
  • 作用:
    • 对数组进行升序排序,使双指针查找两个数的和时能够利用有序性快速调整指针。
    • 初始化 count 用于累计满足条件的三元组数量。

2. 遍历数组

for (int i = 0; i < n - 2; i++) {int target = t - arr[i];int left = i + 1, right = n - 1;
}
  • 作用:
    • 遍历数组的每个元素 arr[i],将其固定为三元组的第一个数 a
    • 计算剩下两个数的目标和 target = t - arr[i]
    • 设置双指针,lefti + 1 开始,right 从数组末尾开始。
  • 边界条件:
    • 由于需要三个不同的数,循环只需要到 n - 2
    • 避免越界错误。

3. 双指针查找两数之和

while (left < right) {if (arr[left] + arr[right] == target) {...} else if (arr[left] + arr[right] < target) {left++;} else {right--;}
}
  • 核心逻辑:
    • arr[left] + arr[right] == target :
      • 找到一组满足条件的对,需要进一步统计并更新结果。
    • arr[left] + arr[right] < target :
      • 总和太小,增加 left 指针以尝试增大总和。
    • arr[left] + arr[right] > target :
      • 总和太大,减小 right 指针以尝试减小总和。

4. 处理双指针值相同的情况

if (arr[left] == arr[right]) { // 左右值相同int num = right - left + 1;count += (long) num * (num - 1) / 2; // 组合数C(num, 2)count %= MOD;break;
}
  • 逻辑:
    • 如果 arr[left] == arr[right],说明所有元素都相等,从中选择两个的组合数为 C(num, 2) = num × (num - 1) / 2
    • 直接更新 count,退出当前循环。

5. 处理双指针值不同的情况

int leftCount = 1, rightCount = 1;// 统计左指针相同值的个数
while (left + 1 < right && arr[left] == arr[left + 1]) {left++;leftCount++;
}// 统计右指针相同值的个数
while (right - 1 > left && arr[right] == arr[right - 1]) {right--;rightCount++;
}// 累加计数
count += (long) leftCount * rightCount;
count %= MOD;left++;
right--;
  • 逻辑:
    • 统计重复值:
      • 使用两个循环分别统计 arr[left]arr[right] 的重复次数。
    • 组合方式:
      • 如果 arr[left]arr[right] 值不同,则可以形成 leftCount × rightCount 对满足条件的组合。
    • 更新 count 并对结果取模,防止溢出。

6. 结果返回

return (int) count;
  • 将结果转换为 int 并返回,确保符合题目要求。
http://www.ds6.com.cn/news/754.html

相关文章:

  • 中国互联网企业排名前十名长沙电商优化
  • 做兼职有哪些靠谱的网站网络营销中的四种方法
  • 给网站做解答是干嘛的整合营销网络推广
  • 西宁做网站最好的公司百度基木鱼建站
  • 无忧网络网站建设百度app下载最新版本
  • 怎么做动漫原创视频网站集客营销软件官方网站
  • wordpress可以拖动百度关键词优化查询
  • 网站标签优化怎么做站长素材
  • 遵义服务好的网站建设公司美国最新消息今天 新闻
  • 淄博网站建设优惠臻动传媒杭州seo推广排名稳定
  • 如何做网站微信小程序百度小说网
  • 北京营销型网站建设网站提交入口链接
  • 工信部网站备案信息怎么查询系统线上销售水果营销方案
  • 南京工程造价信息网c盘优化大师
  • 做网站卖电脑深圳网络推广工资
  • 网站开发技术方案与实施近期10大新闻事件
  • 政府信息公开网站建设的可行性上海做关键词推广企业
  • 做暖暖的视频网站b站视频推广网站动漫
  • 网站如何做360优化专业制作网页的公司
  • 医疗产品网站建设推广app是什么工作
  • 南昌网站建设方案维护微信朋友圈广告投放
  • 网页布局设计方式搜索引擎优化叫什么
  • 岳阳网站建设哪家好百度小程序对网站seo
  • 永平建设有限公司网站长沙网站制作策划
  • 用js做跳转到其他网站百度代运营推广
  • 平台网站开发方案如何做一个自己的电商平台
  • 洛阳天艺网络做网站怎么样网站优化网站
  • 网站建设好处2022年时事政治热点汇总
  • 外贸网站案例自动优化app
  • 第三方免费做网站天津seo关键词排名优化