# 考虑第一个数first for i, (first, idx) in enumerate(nums[:-2]): # 如果发现第i、第i+1、第i+2个数的和加起来超过target # 则更靠后的的选择肯定和更大，直接退出循环 if nums[i][0] + nums[i+1][0] + nums[i+2][0] > target: break # 去重操作，如果遇到连续两个数相等，那么考虑nums[i]和考虑nums[i-1]作为第一个数字 # 所作的计算是一样的。直接跳过nums[i]的计算 if i != 0and nums[i][0] == nums[i-1][0]: continue # 构建相向双指针left和right left, right = i+1, n-1 while left < right: # 计算三个数的和 sum3 = first + nums[left][0] + nums[right][0] # 三数和太大，right左移 if sum3 > target: right -= 1 # 三数和太小，left右移 elif sum3 < target: left += 1 # 三数和等于target，如果三个下标和比之前记录过的三数下标和更小 # 则更新ans_idx else: if sum(ans_idx) > idx + nums[left][1] + nums[right][1]: ans_idx = [idx, nums[left][1], nums[right][1]] # 注意此处，只需要写right -= 1就行，不需要加上left += 1 # 1. 只写right -= 1就可以保证代码不会陷入死循环 # 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right） # 那么while中的left < right条件就一定会有不成立的时候 # 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。 # 如果此时存在 nums[right-1][0] == nums[right][0] # 那么nums[right-1][1]会小于nums[right][1] # i, nums[left][1]和nums[right-1][1]可以构成更小的索引和 # 如果加上了left += 1，可能会漏算全局最小的索引和 right -= 1
# 退出循环，ans_idx为在原数组中的三个数的下标 # 答案需要按照下标大小进行排列 ans_idx.sort() ans = ",".join(str(lst[idx]) for idx in ans_idx) print(ans)
Java
import java.util.*;
publicclassMain{ publicstaticvoidmain(String[] args){ Scanner scanner = new Scanner(System.in);
// 读取一行包含逗号分隔数字的数组 String line = scanner.nextLine();
// 使用 StringTokenizer 分割数字 StringTokenizer tokenizer = new StringTokenizer(line, ","); List lst = new ArrayList<>(); while (tokenizer.hasMoreTokens()) { lst.add(Integer.parseInt(tokenizer.nextToken())); }
// 读取下一行的数字 int target = scanner.nextInt();
// 获得原数组长度 n int n = lst.size(); // 对原 nums 数组进行排序，同时需要记录在原数组中的下标 i，作为排序的第二个依据 List nums = new ArrayList<>(); for (int i = 0; i < n; i++) { nums.add(new Pair(lst.get(i), i)); } Collections.sort(nums);
// 初始化一个长度为 3 的数组，用于储存三个数的下标，初始化均为 n List ansIdx = new ArrayList<>(Arrays.asList(n, n, n));
// 考虑第一个数 first for (int i = 0; i < n - 2; i++) { // 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target
// 则更靠后的选择肯定和更大，直接退出循环 if (nums.get(i).first + nums.get(i + 1).first + nums.get(i + 2).first > target) { break; } // 去重操作，如果遇到连续两个数相等，那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的 // 直接跳过 nums[i] 的计算 if (i != 0 && nums.get(i).first == nums.get(i - 1).first) { continue; } // 构建相向双指针 left 和 right int left = i + 1, right = n - 1; while (left < right) { // 计算三个数的和 int sum3 = nums.get(i).first + nums.get(left).first + nums.get(right).first; // 三数和太大，right 左移 if (sum3 > target) { right--; } // 三数和太小，left 右移 elseif (sum3 < target) { left++; } // 三数和等于 target，如果三个下标和比之前记录过的三数下标和更小 // 则更新 ansIdx else { if (ansIdx.get(0) + ansIdx.get(1) + ansIdx.get(2) > nums.get(i).second + nums.get(left).second + nums.get(right).second) { ansIdx = Arrays.asList(nums.get(i).second, nums.get(left).second, nums.get(right).second); } // 注意此处，只需要写 righ-- 就行，不需要加上 left++ // 1. 只写right -= 1就可以保证代码不会陷入死循环 // 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right） // 那么while中的left < right条件就一定会有不成立的时候 // 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。 // 如果此时存在 nums[right-1][0] == nums[right][0] // 那么nums[right-1][1]会小于nums[right][1] // i, nums[left][1]和nums[right-1][1]可以构成更小的索引和 // 如果加上了 left++ ，可能会漏算全局最小的索引和 right--; } } }
// 退出循环，ansIdx 为在原数组中的三个数的下标 // 答案需要按照下标大小进行排列 Collections.sort(ansIdx); for (int i = 0; i < 3; i++) { System.out.print(lst.get(ansIdx.get(i))); if (i < 2) { System.out.print(","); } } System.out.println(); }
staticclassPairimplementsComparable<Pair> { int first; int second;
// 获得原数组长度 n int n = lst.size(); // 对原 nums 数组进行排序，同时需要记录在原数组中的下标 i，作为排序的第二个依据 vectorint, int>> nums; for (int i = 0; i < n; i++) { nums.push_back({lst[i], i}); } sort(nums.begin(), nums.end());
// 初始化一个长度为 3 的数组，用于储存三个数的下标，初始化均为 n vector<int> ansIdx(3, n);
// 考虑第一个数 first for (int i = 0; i < n - 2; i++) { // 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target // 则更靠后的选择肯定和更大，直接退出循环 if (nums[i].first + nums[i + 1].first + nums[i + 2].first > target) { break; } // 去重操作，如果遇到连续两个数相等，那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的 // 直接跳过 nums[i] 的计算 if (i != 0 && nums[i].first == nums[i - 1].first) { continue; } // 构建相向双指针 left 和 right int left = i + 1, right = n - 1; while (left < right) { // 计算三个数的和 int sum3 = nums[i].first + nums[left].first + nums[right].first; // 三数和太大，right 左移 if (sum3 > target) { right--; } // 三数和太小，left 右移 elseif (sum3 < target) { left++; } // 三数和等于 target，如果三个下标和比之前记录过的三数下标和更小 // 则更新 ansIdx else { if (accumulate(ansIdx.begin(), ansIdx.end(), 0) > nums[i].second + nums[left].second + nums[right].second) { ansIdx = {nums[i].second, nums[left].second, nums[right].second}; } // 注意此处，只需要写 righ-- 就行，不需要加上 left++ // 1. 只写right -= 1就可以保证代码不会陷入死循环 // 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right） // 那么while中的left < right条件就一定会有不成立的时候 // 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。 // 如果此时存在 nums[right-1][0] == nums[right][0] // 那么nums[right-1][1]会小于nums[right][1] // i, nums[left][1]和nums[right-1][1]可以构成更小的索引和 // 如果加上了 left++ ，可能会漏算全局最小的索引和 right--; } } }
// 退出循环，ansIdx 为在原数组中的三个数的下标 // 答案需要按照下标大小进行排列 sort(ansIdx.begin(), ansIdx.end()); for (int i = 0; i < 3; i++) { cout << lst[ansIdx[i]]; if (i < 2) { cout << ","; } } cout << endl;
return0; }
C
#include #include #include #include
// 定义结构体用于存储数值和下标 typedefstruct { int value; int index; } Pair;
