蓝桥杯算法心得——矿石样本分析（贪心+两数之和）

大家好，我是晴天学长，非常类似lc的两数之和，不过就是前期需要优化一下，找到技巧非常重要，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

1) .矿石样本分析

2) .算法思路

1.首先预处理每个值的min（i+1，n-i）。
2.再遍历所有可能出现的x值。
3.t=max（f（x），f（t-x））
4.注意事项：排除x=k-x的情况
5.Java的list要用Arraylist，不然遍历会超时。

3）.算法步骤

4）. 代码实例

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		String[] s = in.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);
		int[] a = new int[n];
		Set<Integer>set = new HashSet<>();
		s = in.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(s[i]);
			set.add(a[i]);
		}
		Map<Integer, Integer>map = new HashMap<>();
		for (int i = 0; i < n; i++) {
			int k1 = a[i];
			if (!map.containsKey(k1)) {
				map.put(k1, Math.min(i+1, n-i));
			}
			int k2 = Math.min(i+1, n-i);
			if (k2<map.get(k1)) {
				map.put(k1, k2);
			}
		}
		int min = Integer.MAX_VALUE;
		List<Integer> list = new ArrayList<>(map.keySet());
		Map<Integer, Integer>map2 = new HashMap<>();
		for (int i = 0; i < list.size(); i++) {
			int x = list.get(i);
			int y = k-x;
			if (y!=x&&map2.containsKey(y)) {
				min = Math.min(min, Math.max(map.get(x), map2.get(y)));
			}
			map2.put(x, map.get(x));
		}
		if (min==Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(min);
		}
	}

}

5）. 总结

• 链表的时间复杂度要知道
  查找
  List list = new ArrayList<>（);（o（1））
  List list = new LinkedList<>();（o（n））
  一般都用ArrayList，除非是修改

试题链接：