Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <map>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- int A[] = {10,20,30,30,20,10,10,20};
- // return (i, j) s.t. A[i] + ... + A[j] is nearest to value c
- pair<int, int> nearest_to_c(int c, int n, int A[]) {
- map<int, int> bst;
- bst[0] = -1;
- // barriers
- bst[-int(1e9)] = -2;
- bst[int(1e9)] = n;
- int sum = 0, start, end, ret = c;
- for (int i=0; i<n; ++i) {
- sum += A[i];
- // it->first >= sum-c, and with the minimal value in bst
- map<int, int>::iterator it = bst.lower_bound(sum - c);
- int tmp = -(sum - c - it->first);
- if (tmp < ret) {
- ret = tmp;
- start = it->second + 1;
- end = i;
- }
- --it;
- // it->first < sum-c, and with the maximal value in bst
- tmp = sum - c - it->first;
- if (tmp < ret) {
- ret = tmp;
- start = it->second + 1;
- end = i;
- }
- bst[sum] = i;
- }
- return make_pair(start, end);
- }
- // demo
- int main() {
- int c;
- cin >> c;
- pair<int, int> ans = nearest_to_c(c, 8, A);
- cout << ans.first << ' ' << ans.second << endl;
- return 0;
- }
- import java.util.*;
- public class FindSubarrayClosestToZero {
- void findSubarrayClosestToZero(int[] A) {
- int curSum = 0;
- List<Pair> list = new ArrayList<Pair>();
- // 1. create prefix array: curSum array
- for(int i = 0; i < A.length; i++) {
- curSum += A[i];
- Pair pair = new Pair(curSum, i);
- list.add(pair);
- }
- // 2. sort the prefix array by value
- Collections.sort(list, valueComparator);
- // printPairList(list);
- System.out.println();
- // 3. compute pair-wise value diff: Triple< diff, i, i+1>
- List<Triple> tList = new ArrayList<Triple>();
- for(int i=0; i < A.length-1; i++) {
- Pair p1 = list.get(i);
- Pair p2 = list.get(i+1);
- int valueDiff = p2.value - p1.value;
- Triple Triple = new Triple(valueDiff, p1.index, p2.index);
- tList.add(Triple);
- }
- // printTripleList(tList);
- System.out.println();
- // 4. Sort by min diff
- Collections.sort(tList, valueDiffComparator);
- // printTripleList(tList);
- Triple res = tList.get(0);
- int startIndex = Math.min(res.index1 + 1, res.index2);
- int endIndex = Math.max(res.index1 + 1, res.index2);
- System.out.println("nnThe subarray whose sum is closest to 0 is: ");
- for(int i= startIndex; i<=endIndex; i++) {
- System.out.print(" " + A[i]);
- }
- }
- class Pair {
- int value;
- int index;
- public Pair(int value, int index) {
- this.value = value;
- this.index = index;
- }
- }
- class Triple {
- int valueDiff;
- int index1;
- int index2;
- public Triple(int valueDiff, int index1, int index2) {
- this.valueDiff = valueDiff;
- this.index1 = index1;
- this.index2 = index2;
- }
- }
- public static Comparator<Pair> valueComparator = new Comparator<Pair>() {
- public int compare(Pair p1, Pair p2) {
- return p1.value - p2.value;
- }
- };
- public static Comparator<Triple> valueDiffComparator = new Comparator<Triple>() {
- public int compare(Triple t1, Triple t2) {
- return t1.valueDiff - t2.valueDiff;
- }
- };
- void printPairList(List<Pair> list) {
- for(Pair pair : list) {
- System.out.println("<" + pair.value + " : " + pair.index + ">");
- }
- }
- void printTripleList(List<Triple> list) {
- for(Triple t : list) {
- System.out.println("<" + t.valueDiff + " : " + t.index1 + " , " + t.index2 + ">");
- }
- }
- public static void main(String[] args) {
- int A1[] = {8, -3, 2, 1, -4, 10, -5}; // -3, 2, 1
- int A2[] = {-3, 2, 4, -6, -8, 10, 11}; // 2, 4, 6
- int A3[] = {10, -2, -7}; // 10, -2, -7
- FindSubarrayClosestToZero f = new FindSubarrayClosestToZero();
- f.findSubarrayClosestToZero(A1);
- f.findSubarrayClosestToZero(A2);
- f.findSubarrayClosestToZero(A3);
- }
- }
- #include<bits/stdc++.h>
- #define M 1000010
- #define REP(i,n) for (int i=1;i<=n;i++)
- using namespace std;
- typedef long long ll;
- ll a[M],n,cum[M],ans=numeric_limits<ll>::max(); //cum->cumulative array
- int main() {
- ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- cin>>n; REP(i,n) cin>>a[i],cum[i]=cum[i-1]+a[i];
- sort(cum+1,cum+n+1);
- REP(i,n-1) ans=min(ans,cum[i+1]-cum[i]);
- cout<<ans; //min +ve difference from 0 we can get
- }
- #include <map>
- #include <stdio.h>
- #include <algorithm>
- #include <limits.h>
- using namespace std;
- #define IDX_LOW_BOUND -2
- // Return [i..j] range of A
- pair<int, int> nearest_to_c(int A[], int n, int t) {
- map<int, int> bst;
- int presum, subsum, closest, i, j, start, end;
- bool unset;
- map<int, int>::iterator it;
- bst[0] = -1;
- // Barriers. Assume that no prefix sum is equal to INT_MAX or INT_MIN.
- bst[INT_MIN] = IDX_LOW_BOUND;
- bst[INT_MAX] = n;
- unset = true;
- // This initial value is always overwritten afterwards.
- closest = 0;
- presum = 0;
- for (i = 0; i < n; ++i) {
- presum += A[i];
- for (it = bst.lower_bound(presum - t), j = 0; j < 2; --it, j++) {
- if (it->first == INT_MAX || it->first == INT_MIN)
- continue;
- subsum = presum - it->first;
- if (unset || abs(closest - t) > abs(subsum - t)) {
- closest = subsum;
- start = it->second + 1;
- end = i;
- if (closest - t == 0)
- goto ret;
- unset = false;
- }
- }
- bst[presum] = i;
- }
- ret:
- return make_pair(start, end);
- }
- int main() {
- int A[] = {10, 20, 30, 30, 20, 10, 10, 20};
- int t;
- scanf("%d", &t);
- pair<int, int> ans = nearest_to_c(A, 8, t);
- printf("[%d:%d]n", ans.first, ans.second);
- return 0;
- }
- public class Solution {
- /**
- * @param nums: A list of integers
- * @return: A list of integers includes the index of the first number
- * and the index of the last number
- */
- public ArrayList<Integer> subarraySumClosest(int[] nums) {
- // write your code here
- int len = nums.length;
- ArrayList<Integer> result = new ArrayList<Integer>();
- int[] sum = new int[len];
- HashMap<Integer,Integer> mapHelper = new HashMap<Integer,Integer>();
- int min = Integer.MAX_VALUE;
- int curr1 = 0;
- int curr2 = 0;
- sum[0] = nums[0];
- if(nums == null || len < 2){
- result.add(0);
- result.add(0);
- return result;
- }
- for(int i = 1;i < len;i++){
- sum[i] = sum[i-1] + nums[i];
- }
- for(int i = 0;i < len;i++){
- if(mapHelper.containsKey(sum[i])){
- result.add(mapHelper.get(sum[i])+1);
- result.add(i);
- return result;
- }
- else{
- mapHelper.put(sum[i],i);
- }
- }
- Arrays.sort(sum);
- for(int i = 0;i < len-1;i++){
- if(Math.abs(sum[i] - sum[i+1]) < min){
- min = Math.abs(sum[i] - sum[i+1]);
- curr1 = sum[i];
- curr2 = sum[i+1];
- }
- }
- if(mapHelper.get(curr1) < mapHelper.get(curr2)){
- result.add(mapHelper.get(curr1)+1);
- result.add(mapHelper.get(curr2));
- }
- else{
- result.add(mapHelper.get(curr2)+1);
- result.add(mapHelper.get(curr1));
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement